Diameter of Binary Tree

Zuerst geht es darum, wie du dich im Array bewegst. Der Knoten am Index i hat sein linkes Kind an 2*i+1 und sein rechtes Kind an 2*i+2, sein Elternknoten befindet sich also an (i-1)/2, abgerundet. Eine Position ist nur dann tatsächlich belegt, wenn ihr Index innerhalb des Arrays liegt und der dortige Wert nicht -1 ist. In [8, 3, 6, 1, 4, -1, -1, -1, -1, 7] hat die 7 am Index 9 ihren Elternknoten am Index 4, und diese 4 hat ihren Elternknoten am Index 1.

Der Durchmesser ist der größte Abstand zwischen zwei Knoten, du kannst also jedes Paar messen. Um den Abstand zwischen den Indizes a und b zu ermitteln, gehst du Schritt für Schritt in Richtung Wurzel, bis sie sich treffen, und zwar immer vom größeren Index aus. Ein größerer Index liegt niemals auf einer höheren Ebene, daher überschreitet dieser Schritt niemals den Treffpunkt. Die Anzahl der Schritte entspricht der Anzahl der Kanten. Für 9 und 2: Die 9 geht zum 4 und dann zum 1, die 2 geht zum 0, und die 1 geht zum 0. Vier Schritte.

Das ist korrekt, aber langsam. Der größte Test ist ein vollständiger Baum mit 16383 Knoten. Dabei entstehen etwa 1.3 × 10^8 Paare, und jedes Paar erfordert bis zu 26 Schritte. Milliarden von Schritten für eine einzige Antwort liegen weit über dem Zeitlimit.

Betrachte den längsten Pfad von seinem höchsten Knoten aus, also dem Knoten, an dem es nicht mehr nach oben, sondern nach unten geht. Von dort geht er so weit wie möglich die linke Seite hinunter und so weit wie möglich die rechte Seite hinunter. Sei height(c) die Anzahl der Knoten auf dem längsten absteigenden Pfad von c, wobei für eine leere Stelle 0 gilt. Dann hat der längste Pfad, der sich am Knoten i wendet, height(2*i+1) + height(2*i+2) Kanten, eine Kante für jeden dieser Knoten.

Probiere also jeden Knoten als Wendepunkt aus und merke dir das beste Ergebnis. Im zweiten Beispiel hat die 5 am Index 1 links die Höhe 2 (1, 3) und rechts ebenfalls 2 (9, 4), also ergibt sich ein Pfad mit vier Kanten. Die Wurzel hat links die Höhe 3 und rechts 0, was nur drei ergibt.

Jeder Aufruf von height durchläuft einen ganzen Teilbaum, und ein Knoten wird für jeden seiner Vorfahren erneut durchlaufen. Der Aufwand beträgt also O(n·h). Bei h ≤ 14 ist das hier schnell genug, aber bei einem kettenförmigen Zeigerbaum kann h bis auf n anwachsen, und dieselbe Idee kostet dann O(n²). Die wiederholten Aufrufe von height sind der unnötige Aufwand, den der letzte Ansatz beseitigt.

Die Höhe eines Knotens hängt nur von den Höhen seiner beiden Kinder ab, und genau diese beiden Zahlen benötigt auch die Prüfung auf den Wendepunkt. Berechne sie also einmal von unten nach oben. Bei einer Postorder-Traversierung werden beide Kinder vor ihrem Elternknoten verarbeitet. An jedem Knoten hast du dann left und right: Aktualisiere die Antwort mit left + right und gib 1 + max(left, right) an den Elternknoten weiter.

Im ersten Beispiel gibt das Blatt 7 den Wert 1 zurück, der darüberliegende Knoten 4 gibt 2 zurück und der Knoten 3 gibt 3 zurück, da sein anderes Kind 1 die Höhe 1 hat. Der Knoten 6 gibt 1 zurück. An der Wurzel ist left + right = 3 + 1 = 4 die Antwort. Jeder andere Knoten erreicht höchstens den Wert 3, nämlich mit 1 + 2 = 3.

Jeder Knoten wird einmal besucht, daher beträgt die Laufzeit O(n). Die Rekursion ist so tief wie der Baum, also O(h), mit etwa einem Stackframe pro Ebene. Die Antwort wird in einer Variablen außerhalb der Rekursion gespeichert, denn was ein Aufruf zurückgibt (eine Höhe), ist nicht das, was du am Ende möchtest (eine Pfadlänge).