python - 使用递归函数获取树的高度

Question

我想解决获取树高度的 cousera 作业。它要求我通过递归函数获取高度。我写了这个函数，但仍然没有得到任何结果。第一行输入是节点数，第二行是一个数字列表，每个数字都指向该节点父节点的索引(-1 值表示该节点是根节点)。

我尝试打印max_height，它给了我一个数字列表。当我调试它时，我发现它首先按异常工作，但在中间当流程返回时，值发生了变化。

def compute_height(n, parents, postion=0, hight=0, max_hight=0, current=0):

    if postion == n-1:
        print(max_hight)
        return max_hight

    if current != -1:
        compute_height(n, parents, postion, hight+1,
                       max(max_hight, hight), parents[current])

    compute_height(n, parents, postion+1, 0, max_hight, postion+1)

它返回无。我该如何解决这个问题？

Answer 1

看来你被递归函数困住了，不知道如何继续。为了有效地完成这项任务，我对其进行了相当大的改变。

一般来说，要解决此类问题，就效率而言最重要的是有一种方法跟踪您已经去过的地方，以便您不 重复不必要的工作。您还需要确保访问树的每一片叶子，因为您不知道哪一片叶子最深。

这里还使用了两个显然非常相关的函数。第一个是驱动程序(1) 函数，当您有一个递归(2) 函数并希望使用一组特定的参数来调用它来启动它时，它通常很有用离开。或者当您想像我在这里那样在 for 循环中运行它时。

如果有什么不合理的地方，请告诉我:

# Computes the height of the tree
def compute_height(n, parents):
    # We make a list to keep track of which nodes have already been visited
    heights = [-1 for x in range(n)]

    # Make sure you visit every node if it is not already visited
    for i, val in enumerate(heights):
        if (val == -1):
            recurse_compute_height(n, parents, i, heights)

    return(max(heights))

# Recursively computes the height for the current node 
def recurse_compute_height(n, parents, index, heights):
    parent = parents[index]

    # Base case for when you reach the root
    if parent == -1:
        return 1

    # Leverage the parent's height, if already computed
    if (heights[parent] != -1):
        heights[index] = heights[parent] + 1
    # Or compute the node's and its parents's height
    else:
        heights[index] = recurse_compute_height(n, parents, parent, heights) + 1

    return heights[index]

# Input and run 
n = 5 
parents = [4, -1, 4, 1, 1, 0]
res = compute_height(n, parents)
print(res)

输出

3