时间戳

首页 > 解决方案 > 求树的高度，输入树可以有任意数量的孩子

python - 求树的高度，输入树可以有任意数量的孩子

问题描述

我的部分问题是编写一个确定树高度的函数。

这是我目前的功能，

def tree_height(node): 
  parent, children = node
  max_height = 0
  for child in children:
    height = tree_height(child)
    if height > max_height:
      max_height = height
  return max_height

但它只返回 0。

* 注意：输入参数应该只有一个，即节点 *

为了，

tree = ("supercalifragilisticexpialidocious",(("a",(("b",(("candy",()),)),("onomatopoeia",()),)),("d",(("egg",(("f",()),)),)),))

输出应该是，

3

标签： pythonrecursiontreetuples

解决方案

您永远不会增加max_height，因此递归调用将始终返回 0；请记住，您比您的孩子高一级。

def tree_height(node): 
    parent, children = node
    max_height = 0
    for child in children:
      child_height = tree_height(child)
      max_height = max(max_height, child_height +  1)
    return max_height

你需要“相信”递归：假设它tree_height(child)给了你孩子的身高。那么你的身高就是你所有孩子的最大身高加一。

编辑：

更 Pythonic 的代码：

def tree_height(node):
  parent, children = node
  return max([tree_height(child) + 1 for child in children]) if children else 0

推荐阅读