Pythonの再帰的な任意のツリーの高さ

Question

私は、バイナリツリーではなく、任意のツリーのツリーの高さを決定する再帰的メソッドを実装しようとしています。我々は2つの入力を与えられ、1つは「n」個の頂点である。 2行目には、頂点の-1からn-1までのn個の整数 が含まれています。それらのi番目のもの（0≤i≤n - 1）が-1の場合、頂点iはルートです。そうでない場合は、i番目の頂点の親の0ベースのインデックスです。正確に1つのルートが存在することが保証されています。入力はツリーを表すことが保証されています。

例えば入力される： N = 5 親= [4、-1、4、1、1] これは、ノード0は、ノード4の子であることを意味し、ノード1がルートであり、ノード2ノード4の子であり、ノード3はノード1の子（ルート）であり、ノード4も同様にルート1のノード1の子である。以来：

4 -1 1 1

出力は、我々は遅い方法より速い方法を実施を担当与えられ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 

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である必要があります。あなたは2度目に木に上がって、それらの値をすべて再計算することを強制されません。