坏树设计，数据结构

Question

我尝试制作一棵树作为我的数据结构课程的一部分。该代码有效但速度极慢，几乎是课程接受时间的两倍。我没有数据结构和算法方面的经验，但我需要优化程序。如果有人有任何提示、建议、批评，我将不胜感激。

树不一定是二叉树。

代码如下：

import sys
import threading

class Node:
    def __init__(self,value):
        self.value = value
        self.children = []
        self.parent = None
    def add_child(self,child):
        child.parent = self
        self.children.append(child)

def compute_height(n, parents):
    found = False
    indices = []
    for i in range(n):
        indices.append(i)
    for i in range(len(parents)):
        currentItem = parents[i]
        if currentItem == -1:
            root = Node(parents[i])
            startingIndex = i
            found = True
            break
    if found == False:
        root = Node(parents[0])
        startingIndex = 0
    return recursion(startingIndex,root,indices,parents)


def recursion(index,toWhomAdd,indexes,values):
    children = []
    for i in range(len(values)):
        if index == values[i]:
            children.append(indexes[i])
            newNode = Node(indexes[i])
            toWhomAdd.add_child(newNode)

            recursion(i, newNode, indexes, values)
        


    return toWhomAdd


def checkHeight(node):
    if node == '' or node == None or node == []:
        return 0
    counter = []
    for i in node.children:
        counter.append(checkHeight(i))
    if node.children != []:
        mostChildren = max(counter)
    else:
        mostChildren = 0
    return(1 + mostChildren)

def main():
    n = int(int(input()))
    parents = list(map(int, input().split()))
    
    root = compute_height(n, parents)
    print(checkHeight(root))
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()

编辑：

对于这个输入（第一个数字是节点的数量，其他数字是节点的值）

5
4 -1 4 1 1

我们期望这个输出（树的高度）

另一个例子：

输入：

5
-1 0 4 0 3

输出：

Answer 1

它看起来像为节点指定的 value 是另一个节点（其父节点）的索引引用。问题中没有说明这一点，但是如果该假设是正确的，那么您实际上并不需要使用 Node 个实例创建树。只需将输入读入列表（你已经这样做了），你实际上有编码在其中的树。

例如，列表 [4, -1, 4, 1, 1] 表示这棵树，其中标签是此列表中的索引：

根据维基百科给出的定义，这棵树的 height 应该是 2。但显然预期结果是 3，这是最长路径上的节点数（不是边数）叶子的根，或者 - 换句话说 - 树中级别的数量。

用递归的思路是对的，但是可以自下而上（从任意节点开始），递归得到父节点的结果，将1加1。利用动态规划的原理，存储每个节点的结果在一个单独的列表中，我称之为 levels:

def get_num_levels(parents):
    levels = [0] * len(parents)

    def recur(node):
        if levels[node] == 0:  # this node's level hasn't been determined yet
            parent = parents[node]
            levels[node] = 1 if parent == -1 else recur(parent) + 1
        return levels[node]

    for node in range(len(parents)):
        recur(node)

    return max(levels)

主要代码可以是你所拥有的：

def main():
    n = int(int(input()))
    parents = list(map(int, input().split()))
    
    print(get_num_levels(parents))

坏树设计，数据结构

Bad Tree design, Data Structure

python

tree

recursion

binary-tree

data-structures