不使用列表查找树的高度

Question

def height(t):
''' (Tree) -> int

Return 1 + the number of nodes in longest path in Tree t.

>>> tree = Tree(23)
>>> height(Tree)
1
>>> tree = descendents_from_list(Tree(11), [2, 3, 4, 5, 6], 3)
>>> height(tree)
3
'''
num = 1
for i in t.children:
    if i.children:
       num += height(i)
return num

对于带有 t.value 和 t.children 的上述函数，我需要弄清楚如何在不使用列表的情况下找到高度。就像我需要找到一种方法在不跟踪父树的情况下递归地沿着树向下走。

我试过了，还是想不通。有人可以帮我解决这个问题吗？

Answer 1

基本思路是这样的，树的高度是由树中最长的路径决定的。那么如果我们正在查看一个有子节点的节点，任何节点，我们要关注哪个子节点的高度？最高高度的子节点对吧？在 Python 中，我们可以使用内置的 max 函数获取任何可迭代值集中的最大值。在这一过程中的每一点，我们都希望将所有子树中的最大高度加 1。

所以现在我们只需要递归的基本情况，即如果节点没有子节点我们该怎么办？只是 return 1.

下面的代码说明了这个算法：

def height(t):
    if not t.children:
        return 1
    else:
        return max(height(c) for c in t.children) + 1

Answer 2

你能像这样创建一个函数吗

num = 1
def height(t):
    global num
    child = [i for i in t if i.children]
    if child:
        num += 1
        height(child) #reccursing
    else:
        return num

不使用列表查找树的高度

Finding height of tree without using list

python

recursion

tree

height