python - 计算任意(非二叉)树的高度

Question

我目前正在学习在线数据结构类(class)，这是其中一项家庭作业；请引导我找到答案，而不是给我答案。

提示如下:

Task. You are given a description of a rooted tree. Your task is to compute and output its height. Recall that the height of a (rooted) tree is the maximum depth of a node, or the maximum distance from a leaf to the root. You are given an arbitrary tree, not necessarily a binary tree.

Input Format. The first line contains the number of nodes n. The second line contains integer numbers from −1 to n−1 parents of nodes. If the i-th one of them (0 ≤ i ≤ n−1) is −1, node i is the root, otherwise it’s 0-based index of the parent of i-th node. It is guaranteed that there is exactly one root. It is guaranteed that the input represents a tree.

Constraints. 1 ≤ n ≤ 10⁵.

我当前的解决方案有效，但当 n > 10² 时速度非常慢。这是我的代码:

# python3

import sys
import threading

# In Python, the default limit on recursion depth is rather low,
# so raise it here for this problem. Note that to take advantage
# of bigger stack, we have to launch the computation in a new thread.
sys.setrecursionlimit(10**7)  # max depth of recursion
threading.stack_size(2**27)   # new thread will get stack of such size
threading.Thread(target=main).start()

# returns all indices of item in seq
def listOfDupes(seq, item):
    start = -1
    locs = []
    while True:
        try:
            loc = seq.index(item, start+1)
        except:
            break
        else:
            locs.append(loc)
            start = loc
    return locs

def compute_height(node, parents):
    if node not in parents:
        return 1
    else:
        return 1 + max(compute_height(i, parents) for i in listOfDupes(parents, node))

def main():
    n = int(input())
    parents = list(map(int, input().split()))
    print(compute_height(parents.index(-1), parents))

示例输入:
>>> 5
>>> 4 -1 4 1 1
这将产生 3 的解决方案，因为根是 1、3 和 4 分支 1，然后 0 和 2 从 4 分支出来，这使得这棵树的高度为 3.

如何改进此代码以使其在 3 秒的时间基准下？另外，用另一种语言会更容易吗？

Answer 1

只要算法正确，Python 就可以。由于您只是在寻求指导，请考虑:

1) 如果知道父节点的深度，我们就知道节点的深度；和2) 我们对树的结构不感兴趣，所以我们可以丢掉不相关的信息。

根节点指针的值为-1。假设我们用值 -2 替换它的 child 指向根节点的指针，用 -3 替换他们的 child 的指针，等等。这些中最大的绝对值是树的高度。

如果我们从任意节点 N(0) 遍历树，我们可以在节点 N(k) 遇到负值时立即停止，此时我们可以用其父节点的值替换每个节点，减去一。即，N(k-1) = N(k) -1，N(k-2)=N(k-1) - 1 ... N(0) = N(1) -1。随着越来越多的指针被它们的深度所取代，每次遍历更有可能因遇到深度已知的节点而终止。事实上，这个算法基本上是线性时间。

因此:将数据加载到数组中，从第一个元素开始遍历指针，直到遇到负值。构建另一个遍历的节点数组。当遇到负值时，使用第二个数组将第一个数组中的原始值替换为它们的深度。对第二个元素执行相同操作，依此类推。跟踪您遇到的最大深度:这就是您的答案。