Funktion finde die tiefste Summe eines binären Suchbaums

Question

Ich versuche, eine Funktion in Python zu machen, wo ich die BST-Klasse überhaupt nicht ändern möchte, um dies zu tun. Die Funktion besteht darin, die Summe des Pfades der Wurzel zum Knoten mit der höchsten Tiefe zu finden. Wenn es mehrere Knoten gibt, die dieselbe Tiefe haben, suche ich die maximale Summe davon und gebe sie zurück.

Was habe ich bisher (eine grundlegende BST Klasse verwenden)

Klasse BTnode (Objekt):

def __init__(self, data, left=None, right=None): 

     self.data = data 
     self.left = left 
     self.right = right 

Nach dem Versuch, einen Algorithmus zu machen dies für eine Weile zu lösen, kam ich mit ein paar oben, aber sie waren fehlgeschlagen und ich wusste nicht, wie man es programmiert.

ALGORITHM:

ich denke, das würde funktionieren:

Wir von der Wurzel beginnen. (Der Basisfall, denke ich, sollte immer dann sein, wenn wir ein Blatt treffen, als wenn kein Kind in einem Knoten ist, also kein linkes oder rechtes Kind, und auch wenn es links kein Recht gibt, oder wenn es ein Recht gibt, nicht links)

Ich überprüfe den linken Teilbaum zuerst und bekomme die Tiefe davon, wir nennen es auch depth_L mit der Summe. Dann überprüfe ich den rechten Teilbaum und wir nennen ihn depth_R und erhalten dann die Tiefe und die Summe.

Die zweite Bedingung wäre zu prüfen, ob sie gleich sind, ob sie gleich sind oder nicht, und wir nehmen einfach die maximale Summe von zwei Tiefen. Sonst würden wir sehen, wer die höchste Tiefe hat und versuchen, die Summe davon zu bekommen.

Jetzt wo ich weiß nicht, wie es geht, ist ein paar Dinge.

1: Ich habe nie gelernt, optionale Parameter, so versuche ich zu vermeiden, während dieser Übung, aber ich glaube nicht, dass ich kann und ich würde wirklich schätzen, jemand könnte mir einige coole Hilfsfunktionen stattdessen.

2: Es ist nicht die Summe der rechten Seite oder der linken Seite ist der Weg, den ich brauche. Seine Art verwirrend eine Art und Weise zu denken, nur den Pfad

(Heres mein erneuter Versuch mit dem Algorithmus oben) zu erhalten:

def deepest_sum(self, bsum = 0, depth = 0): 

     # The root is in every path so 
     bsum = bsum + self.data 
     depth = depth + 1 
     # Base case whenever we find a leaf 
     if self.left == None and self.right == None: 
      result = bsum,depth 

     elif self.left is not None and self.right is None: 
      pass 

     elif self.left is None and self.right is not None: 
      pass 

     else: 

      # Getting the left and right subtree's depth as well as their 
      # sums, but once we hit a leaf it will stop 
      # These optional parameters is messing me up 
      if self.left: 
       (sums1, depth_L) = self.left.deepest_sum(bsum,depth) 
      if self.right: 
       (sums2, depth_R) = self.right.deepest_sum(bsum,depth) 

      # The parameter to check if they are equal, the highest goes through 
      if depth_L == depth_R: 
       result = max(sums1, sums2), depth_R 
      else: 
       if depth_L > depth_R: 
        result = sums1, depth_L 
       else: 
        result = sums2, depth_R 

     return result 

Fest auf den Teilen i erwähnt. Heres ein Beispiel:

>>> BST(8, BST(7, BST(10), BST(11)), BST(6, BST(11), BST(9, None, BST(14))) 

37 (depth 3 is the highest so 8 + 6 + 9 + 14 is the path) 

Leider i BST legte ich ihr nur vergessen, einen binären Baum nicht BST.

Ich weiß, meins gibt ein Tupel, aber ich kann immer eine Hilfsfunktion machen, um das zu beheben, ich dachte nur, es wäre leichter, den Überblick über die Knoten zu behalten.

Answer 1

Sie könnten die Implementierung ein wenig vereinfachen, wenn die Funktion keine Methode von BTNode sein muss. Dann können Sie den Überblick über die Tiefe behalten & Summe, iterieren nach das Blatt und die aktuelle Tiefe und Summe zurückgeben.Zusätzlich, wenn Sie (depth, sum) Tupel zurückgeben können Sie sie direkt gegeneinander mit max vergleichen:

class BTNode(object): 
    def __init__(self, data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 

def deepest_sum(node, depth=0, current=0): 
    # Base case 
    if not node: 
     return (depth, current) 

    depth += 1 
    current += node.data 

    return max(deepest_sum(node.left, depth, current), 
       deepest_sum(node.right, depth, current)) 

tree = BTNode(8, BTNode(7, BTNode(10), BTNode(11)), BTNode(6, BTNode(11), BTNode(9, None, BTNode(14)))) 
print(deepest_sum(tree)) 

Ausgang:

(4, 37)