Maximale Tiefe eines Binärbaum in Python

Question

habe ich ein Tupel aus einem binären Baum und es sieht so aus:

tuple = (1, (2, (4,5,6), (7, keine, 8)), (3,9, (10,11,12)))

die Baumstruktur wird klarer, indem Einbuchtung:

 (1, 
    (2, 
     (4, 
      5, 
      6 
     ), 
     (7, 
      None, 
      8 
     ) 
    ), 
    (3, 
     9, 
     (10, 
      11, 
      12 
     ) 
    ) 
) 

ich weiß, wie das Maximum finden Tiefe des binären Baumes mit rekursiver Methode, aber ich versuche, die maximale Tiefe us zu finden Ich habe das Tupel erstellt, das ich erstellt habe. Kann mir jemand helfen, wie es geht?

Answer 1

rekursive Methode:

a = (1,(2,(4,5,6),(7,None,8)),(3,9,(10,11,12))); 

def depth(x): 
    if(isinstance(x, int) or x == None): 
     return 1; 
    else: 
     dL = depth(x[1]); 
     dR = depth(x[2]); 
     return max(dL, dR) + 1; 

print(depth(a)); 

Die Idee ist, die Tiefe des Baumes zu bestimmen, indem an seinem linken und rechten Teilbaum suchen. Wenn der Knoten keine Unterbäume hat, wird eine Tiefe von 1 zurückgegeben. Andernfalls gibt es max zurück (Tiefe rechts, Tiefe links) + 1

Answer 2

Hier ist eine knifflige, aber ziemlich effiziente Lösung, die funktioniert, vorausgesetzt, dass keine Elemente Ihrer Datenstruktur eine Zeichenfolge ist, die '(' oder ')' enthält. Ich würde das Tupel in eine Zeichenfolge konvertieren und es analysieren, um die Tiefe der Klammern zu zählen.

string = str(myTuple) 

currentDepth = 0 
maxDepth = 0 
for c in string: 
    if c == '(': 
     currentDepth += 1 
    elif c == ')': 
     currentDepth -= 1 

    maxDepth = max(maxDepth, currentDepth) 

Es gibt die Tiefe in einer linearen Zeit in Bezug auf die Anzahl der Zeichen in der Zeichenkette in dem die Tupel umgewandelt. Diese Zahl sollte mehr oder weniger proportional zur Anzahl der Elemente plus der Tiefe sein, sodass Sie eine Komplexität haben, die ungefähr gleich O(n + d) ist.

Answer 3

class Node(object): 
    def __init__(self, x): 
     self.val = x 
     self.left = None 
     self.right = None 

class Solution(object): 
    def maxDepth(self, root): 
     if not root: 
      return 0 
     ldepth = self.maxDepth(root.left) 
     rdepth = self.maxDepth(root.right) 
     return max(ldepth, rdepth) + 1