Python在T中得到所有子代的高度

Question

我在可视化一种递归地获取普通树（nonBST）中所有子节点高度的方法时遇到了困难。在

对于BST，这是相当明显的，因为只有两个节点。考虑到每个节点可能有多个子节点，您将如何做到这一点？在

你将如何获得一个普通树中所有子节点高度的列表？在

我不能画一幅画，因为我有10个以下的代表，但假设我有一棵树有多个孩子。这些子节点中的每一个子节点在末尾都指向不同的叶节点。我需要从根节点到叶节点的每个路径的高度列表。你打算怎么做？在

我知道：

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

显然会返回max高度，但我想不出一种方法可以递归地对到达树末尾的每个路径执行此操作。我不想要最高的高度，我想要所有的高度。在

Answer 1

这很简单，您应该传递另一个参数level，它由1+节点和根之间的连接数定义

当您到达一个叶时，您将级别值添加到全局列表中，此时级别值将是从根到叶之间的路径长度

运行结束时，全局列表将包含所有高度

heights = []

def height(t, level=0):
    if not t.children:
        heights.append(level)
    else:
        for c in t.children:
            height(c, level+1)