找到树的高度，其中输入树可以有很多孩子

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。

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

for，

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

输出应该是

3

Answer 1

您永远不会增加 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

Answer 2

我认为您在正确的轨道上，但是问题是您可能不了解递归height = tree_height(child)，因为如果没有孩子，它将返回0，最终将返回0(您的情况(

您应该做的是将功能放入另一个参数，该参数将计算深度

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

尝试一下此代码，然后下次在纸上写/绘制它，以查看它是什么是在做什么 不要在此处发布您的算法家庭作业：(