python - 查找树的高度，其中输入树可以有任意数量的子树

Question

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

这是我当前的功能，

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

Answer 1

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

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)给出了您 child 的高度。那么您的高度就是您所有 child 的最大高度加一。

编辑:

更Pythonic的代码:

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