python 中的递归任意树高

Question

我正在尝试实现一种递归方法来确定任意树的树高，而不是二叉树。我们有两个输入，一个是 'n' 顶点数。第二行包含n个整数从 −1 到 n − 1 parents 个顶点。如果i-th其中一个（0≤i≤n-1）为-1，则顶点i为根，否则为i-th顶点的parent的从0开始的索引。保证只有一个根。保证输入代表一棵树。

例如输入是： n = 5 parent = [4, -1, 4, 1, 1] 这意味着节点 0 是节点 4 的 child，节点 1 是根，节点 2 是节点 4 的 child，节点 3 是节点 1 的 child（根) 并且节点 4 同样是节点 1 的 child 根。自：

0 1 2 3 4

4 -1 4 1 1

输出将是树的高度 3。我们得到了一个慢速方法，任务是实现一个更快的方法。恐怕我看不到如何将节点输入输入到类似的东西：

Height(tree)
if tree = null:
    return 0
else:
    return 1 + Max(Height(tree.child)) 
    # I realise this is a max of one value

提前致谢！

# 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

n = 5
parent = [4, -1, 4, 1, 1]

class TreeHeight:
    def read(self, n, parent):
        self.n = n
        self.parent = parent

    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(n, parent)
    print(tree.compute_height())

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

Answer 1

我相信你要找的是 memoization:

天真的实现，对于每个节点，查看到根的整个路径，存储该高度，然后重新计算它......一遍又一遍。

通过记忆，您可以将已完成的计算保存在备忘录中：

例如：

节点 0 有高度 3，但发现您已经找到节点 4 的高度，因此您可以存储该信息 (2)。

然后，当你找到节点 2 的高度时，它的父节点是节点 4，你已经知道它是 2...因此节点 2 的高度必须是 3。您不会被迫第二次上树并重新计算所有这些值。

Answer 2

我想我可以用下面的代码更快地解决这个问题。我构建树并找到根。然后递归调用类似于上面伪代码的函数。

我得到了正确的答案，但有人可以帮助我了解这是否是最佳方式并且速度更快吗？我对编程很陌生。根据我的理解，函数 "compute_height(self)" 的时间复杂度是 O(n^2) 而树构造和 "compute_height_nodes" 的时间复杂度都是 O(n)?

谢谢

`

class Node:
    def __init__(self,name):
    self.key = name
    self.child = []

class TreeHeight:

    def __init__(self):
        self.n = int(input())
        self.input = [int(i) for i in input().split()]
        self.root = None
        self.nodes = []


    def read(self): #construct the tree
        noes = []
        for i in range(self.n): 
            noes.append(Node(i))
        j=0
        for i in self.input:    
            if i != -1:
                noes[i].child.append(noes[j])
            else:
                self.root = noes[j]
            j += 1
        self.nodes = noes

    def compute_height_nodes(self):
        node = self.root
        def Height(node):
            if node is None:
                return 0
            if len(node.child)==0:
                return 1
            else:
                h = []
                for i in range(len(node.child)):
                    h.append(Height(node.child[i]))

            return 1 + max(h)
        return Height(node)


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

if __name__ == "__main__":
    main()`

python 中的递归任意树高

Recursive arbitrary tree height in python

python

algorithm

tree

recursion