简介

我正在学习edX的课程，并且已经花了3个小时的时间来完成这个练习作业，但是我仍然找不到一种方法来实现这个方法，而不会花费太长的时间，并且会使自动分级机超时。
我尝试了3种不同的方法，都是做同样的事情，包括2种递归方法和1种非递归方法（我最新的）。
我认为我的代码存在的问题是，查找子节点的方法太长了，因为它必须遍历整个节点列表。

输入和输出格式

输入包括第一行上的N，其为第2行上给出的列表的大小。

• 范例：*

5
-1 0 4 0 3

若要从此生成树：数组中的每个值都是指向数组中另一个索引的指针，因此在上面的示例中，0是-1（索引0）的子节点。由于-1不指向其他索引，因此它是根节点。

范例中的树形结构具有根节点-1，它有两个子系0（索引1）和0（索引3）。索引1的0没有子系，索引3的0有1个子系：3（索引4），而该子节点又只有一个子节点4（索引2）。
上述输入产生的输出为4。这是因为包含-1（根节点）、0、3和4的分支的最大高度为4，而另一个分支（-1和0）的高度为2。
如果你需要更详细的解释，那么我可以在评论中再给予一个例子！
输出是树的最大高度。输入的大小达到了100，000这是我遇到的麻烦，因为它必须在正好3秒或低于的时间内完成。
我的代码
这是我最新的非递归方法，我认为这是我做的最快的方法（仍然不够快）。我使用了网站上的启动程序，我也会在我的代码下面包括它。无论如何，谢谢你的帮助！
我的代码：

# python3

import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

def height(node, parent_list):
        h = 0
        while not node == -1:
                h = h + 1
                node = parent_list[node]
        return h + 1

def search_bottom_nodes(parent_list):
        bottom_nodes = []
        for index, value in enumerate(parent_list):
                children = [i for i, x in enumerate(parent_list) if x == index]
                if len(children) == 0:
                        bottom_nodes.append(value)

        return bottom_nodes

class TreeHeight:
        def read(self):
                self.n = int(sys.stdin.readline())
                self.parent = list(map(int, sys.stdin.readline().split()))

        def compute_height(self):
                # Replace this code with a faster implementation
                bottom_nodes = search_bottom_nodes(self.parent)
                h = 0
                for index, value in enumerate(bottom_nodes):
                        h = max(height(value, self.parent), h)
                return h

def main():
  tree = TreeHeight()
  tree.read()
  print(tree.compute_height())

threading.Thread(target=main).start()

edX启动器：

# python3

import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

class TreeHeight:
        def read(self):
                self.n = int(sys.stdin.readline())
                self.parent = list(map(int, sys.stdin.readline().split()))

        def compute_height(self):
                # Replace this code with a faster implementation
                maxHeight = 0
                for vertex in range(self.n):
                        height = 0
                        i = vertex
                        while i != -1:
                                height += 1
                                i = self.parent[i]
                        maxHeight = max(maxHeight, height);
                return maxHeight;

def main():
  tree = TreeHeight()
  tree.read()
  print(tree.compute_height())

threading.Thread(target=main).start()