Wie man die Höhe eines Knotens im Binärbaum rekursiv findet

path = 0 # the lenght of the path while self.right != None or self.left != None: while self.right != None: self = self.right path = path +1 while self.left != None: self = self.left path = path +1 return path 

Dies ist mein Beispielcode für die Suche nach der Höhe, ist definiert als die Länge des längsten Pfades durch Anzahl der Knoten von Selbst zu einem Blatt. Die Höhe eines Blattknotens beträgt 1.

Es funktioniert nicht

  • Wie generiere ich alle Permutationen einer Liste in Python
  • Python-Algorithmische Aussage
  • Wie kann festgestellt werden, ob zwei Partitionen (Clusterings) von Datenpunkten identisch sind?
  • Längste wiederholte (k-mal) Teilstring
  • Berechnen Sie die Ähnlichkeit zwischen zwei Listen
  • Verbesserung der Zusammenführung sortieren
  • Längste zunehmende Teilsequenz
  • Algorithmus für die Suche nach Multiset Permutation gegeben lexikographischen Index
  • 2 Solutions collect form web for “Wie man die Höhe eines Knotens im Binärbaum rekursiv findet”

    Was du tust, ist nicht rekursiv, es ist iterativ. Rekursiv wäre so etwas wie:

     def height(node): if node is None: return 0 else: return max(height(node.left), height(node.right)) + 1 

    Sie erhielten die Lösung von mata, aber ich schlage vor, Sie schauen auch auf Ihren Code und verstehen, was es tut:

      while self.right != None: self = self.right path = path +1 

    Was wird das tun? Es wird das richtige Kind finden, dann sein rechtes Kind und so weiter. Das prüft also nur einen Pfad des "rechts oben".

    Das tut das gleiche für die linke:

      while self.left != None: self = self.left path = path +1 

    Die Idee in der Rekursion ist, dass für jedes Teilproblem, Sie es mit dem exakt gleichen Rezept für alle anderen Teilprobleme lösen. Also, wenn du deinen Algorithmus nur auf einen Teilbaum oder ein Blatt anwenden würdest, würde es noch funktionieren.

    Auch eine rekursive Definition nennt sich selbst (obwohl man dies mit einer Schleife implementieren kann, aber das geht hier über den Rahmen hinaus).

    Remeber die Definition:

    Rekursion: siehe Definition der Rekursion.

    😉

    Python ist die beste Programmiersprache der Welt.