1

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

这是我目前的功能，

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
4

2 回答 2

2

您永远不会增加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
于 2019-07-03T08:19:02.507 回答
0

我认为你在正确的轨道上，但问题是你可能不理解递归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

试试这个代码，下次在纸上写/画，看看它在做什么+不要在这里发布你的算法作业:)

于 2019-07-03T08:14:39.540 回答