Rekursive arbiträre Baumhöhe in Python

Question

Ich versuche eine rekursive Methode zu implementieren, um die Baumhöhe eines beliebigen Baumes, nicht eines binären Baumes zu bestimmen. Wir haben zwei Eingaben, eins ist 'n' die Anzahl der Ecken. Die zweite Zeile enthält n Integerzahlen von -1 bis n - 1 Eltern von Vertices. Wenn der i-te eine von ihnen (0 ≤ i ≤ n - 1) -1 ist, ist Vertex i die Wurzel, andernfalls ist es der 0-basierte Index des Elternteils des i-ten Vertex. Es ist garantiert, dass es genau eine Wurzel gibt. Es ist garantiert, dass die Eingabe einen Baum darstellt.

Zum Beispiel ist ein Eingang: n = 5 parent = [4, 1, 4, 1, 1] Dies bedeutet, dass der Knoten 0 ist ein Kind des Knotens 4, den Knoten 1 die Wurzel, Knoten 2 ist ein Kind von Knoten 4, Knoten 3 ist ein Kind von Knoten 1 (der Wurzel) und Knoten 4 ist ebenfalls ein Kind von Knoten 1 der Wurzel. Seit:

4 -1 4 1 1

Der Ausgang wäre die Höhe des Baumes der 3. wir eine langsame Methode gegeben sind eine mit der Umsetzung eine schnellere Methode beauftragt . Ich fürchte, ich kann nicht sehen, wie die Knoten Eingänge in etwas wie eingeben:

Vielen Dank im Voraus!

# 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

Ich glaube, was Sie suchen ist memoization:

Die naive Implementierung, für jeden Knoten, schaut auf den gesamten Pfad zur Wurzel, speichert die Höhe, neu berechnet es dann ... über und über.

Mit memoization, halten Sie ein Memo von Berechnungen haben Sie bereits getan:

Zum Beispiel:

Knoten 0 Höhe hat 3, aber festgestellt, dass Sie bereits Knoten 4 Höhe gefunden, so können Sie speichern Sie diese Informationen (2).

Dann, wenn Sie die Höhe von Knoten 2 finden, ist der Vater Knoten 4, von dem Sie bereits wissen, dass er 2 ist ... daher muss die Höhe von Knoten 2 3 sein. Du bist nicht gezwungen, ein zweites Mal den Baum hinaufzugehen und all diese Werte neu zu berechnen.