计算任意（非二叉）树的高度

Question

我目前正在学习在线数据结构课程，并且这是其中一个作业任务; 请指导我如何得到答案，而不是给我答案。

以下是任务描述：

任务：给定一棵根树的描述。您的任务是计算并输出其高度。回想一下，(根)树的高度是节点的最大深度，或从叶子到根的最大距离。给定任意树，不一定是二叉树。

输入格式：第一行包含节点数n。第二行包含整数号码从-1到n-1的父节点。如果它们中的第i个(0 ≤ i ≤ n-1)为-1，则节点i为根，否则它是第i个节点的基于0的索引的父节点。可以保证只有一个根。可以保证输入表示一棵树。

约束条件：1 ≤ n ≤ 10^5.

我的当前解决方案有效，但当n>10^2时非常缓慢。以下是我的代码:

# 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秒的时间基准下运行？此外，在另一种语言中是否更容易实现？

- Josh

---

生成单个线程没有任何优势，只会增加开销。生成一组线程来解决问题的不同部分可能有所帮助，但是Python具有GIL，除非进行IO操作，否则可能没有太大用处。 - AChampion

你有输入示例吗？ - AChampion

@AChampion 我在我的问题中添加了示例输入。此外，我另外启动了一个线程，因为由于某些测试用例的大小，这是该问题推荐的做法。无论如何，我不认为这会导致我的时间问题，你觉得呢？ - Josh

Answer 1

只要算法正确，Python就可以胜任。由于您只是在寻求指导，请考虑以下内容：

1）我们知道一个节点的深度当且仅当其父节点的深度已知；而且 2）我们不关心树的结构，所以我们可以抛弃无关信息。

根节点指针的值为-1。假设我们用-2替换其子节点指向根节点的指针，用-3替换它们的子节点指针，以此类推。这些值的最大绝对值就是树的高度。

如果我们从任意节点N(0)遍历树，只要在节点N(k)处遇到负值，我们就可以停止遍历。此时，我们可以将每个节点替换为其父节点的值减1。即，N(k-1) = N(k) -1，N(k-2)=N(k-1) - 1... N(0) = N(1) -1。随着更多指针被其深度替换，每次遍历都越来越有可能通过遇到深度已知的节点而终止。实际上，这个算法基本上需要线性时间。

因此：将数据加载到数组中，从第一个元素开始遍历指针，直到遇到负值为止。在遍历过程中，建立另一个数组存储经过的节点。当您遇到负值时，使用第二个数组替换第一个数组中的原始值为它们的深度。对第二个元素以此类推。跟踪您遇到的最大深度：那就是您的答案。

- Joe

Answer 2

这个问题的结构看起来最好从底向上解决，而不是从顶向下。你的自上而下的方法会浪费时间去寻找，这是不必要的，例如：

def height(tree):
    for n in tree:
        l = 1
        while n != -1:
            l += 1
            n = tree[n]
        yield l

In []:
tree = '4 -1 4 1 1'
max(height(list(map(int, tree.split()))))

Out[]:
3

或者，如果您不喜欢生成器：

def height(tree):
    d = [1]*len(tree)
    for i, n in enumerate(tree):
        while n != -1:
            d[i] += 1
            n = tree[n]
    return max(d)

In []:
tree = '4 -1 4 1 1'
height(list(map(int, tree.split())))

Out[]:
3

上述方法是暴力算法，因为它没有利用已经访问过的树的部分进行重复利用，添加这一功能应该不会太难。

- AChampion

---

你的代码片段涉及到一个未定义的 d。看起来它可能是从你删除的优化中留下来的，或者类似于那样的东西。 - user2357112

@user2357112 你是正确的，剩下的快捷方式代码已经被移除了。 - AChampion

我在http://thanglongit.net:8000/problem/cf212computetreeheig上发现了相同的问题-使用修剪提交了上述内容，并通过了测试：2.83秒内320/320。 - AChampion

Answer 3

你的算法在搜索输入中数字位置时花费了很多时间。如果你只是一遍遍历输入，当你找到每个数字时记录它们的位置，那么你就不必再后面重复搜索。考虑什么数据结构能够有效地记录这些信息。

- user2357112