Thema:
Maximale Pfadsumme binärer Baum
Finden Sie bei einem binären Baum die maximale Pfadsumme.
Der Pfad kann an jedem Knoten im Baum beginnen und enden.
Zum Beispiel:
Angesichts des folgenden binären Baums,
1 / / 2 3
Rückkehr 6.
Der Knoten kann negativ sein und nach einem größten Weg suchen, so dass die durchlaufenen Knoten die größten sind. Der Pfad kann an jedem Knoten beginnen und enden, kann aber nicht zurückgehen.
Obwohl diese Frage ungewöhnlich aussieht, werden Sie, wenn Sie darüber nachdenken, feststellen, dass sie nichts anderes als die Durchführung von binären Bäumen + einfache dynamische Planungsideen ist.
Wir können das Problem trennen: Auch wenn der letzte größte Weg nicht durch den Wurzelknoten führt, muss er seinen eigenen "höchsten Punkt" haben. Daher müssen wir nur für alle Knoten herausfinden: Wenn der Pfad diesen Knoten als "höchster Punkt" nimmt, wie hoch ist die maximale Länge des Pfades? Hinweis als max. Finden Sie dann den Maximalwert Max in Max, was das Ergebnis ist, nach dem Sie suchen. Die gleiche Idee wie "die größte kontinuierliche Sequenz in einer ganzzahligen Sequenz zu finden".
Im Folgenden finden Sie die Beziehung zwischen max, die jedem "höchsten Punkt" entspricht.
Nehmen wir den Stammknoten als Beispiel. Die Berechnungsmethode für den maximalen Pfad, der durch den Wurzelknoten führt, lautet:
Wir finden die maximale Pfadlänge A im linken Unterbaum mit dem linken Kind als Startpunkt und die maximale Pfadlänge B im rechten Subtree mit dem rechten Kind als Ausgangspunkt. Dann der max = max dieses Punktes (a+b+node.val, a+node.val, b+node.val, node.val)
Daher definieren wir eine Funktion zur Berechnung von A oder B oben. Sein Parameter ist ein Knoten und sein Rückgabewert ist die maximale Pfadlänge. Der Ausgangspunkt dieses Pfades muss jedoch der Eingangsknoten sein, und der Pfad muss sich auf einem Unterbaum mit dem Startpunkt als Stammknoten befinden.
Dann kann der Rückgabewert des Funktionsfunktions (Knoten) wie folgt definiert werden: returnmax (func (node.left)+knoten.val, func (knoten.right)+node.val, node.val)
Die Terminierungsbedingung ist Node == NULL und gibt 0 direkt zurück.
Dann fanden wir, dass der obige Prozess der Berechnung von Max und Berechnung von Max vollständig in den Func (Knoten) eingebaut werden kann.
Gemäß dem Code dieser Idee ist MaxPathsumcore die obige Implementierung von Func (Knoten):
/** * Definition für binärer Baum * struct treenode { * int val; * Treenode * links; * Treenode * rechts; * Treenode (int x): val (x), links (null), rechts (null) {} *}; */class -Lösung {public: int maxpathsum (treenode *root) {maxpathsumcore (root); return max;} int maxpathsumcore (treenode *node) {if (null == node) return 0; int a = maxpathsumcore (node -> links); rechts); if ((a+b+node-> val)> max) max = (a+b+node-> val); if ((a+node-> val) max) max = (a+node- maxviathisnode = ((a + node-> val)> node-> val? (a + node-> val): node-> val);Zeitkomplexität O (n), n ist die Gesamtzahl der Knoten.
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels über die Codeanalyse des maximalen Pfades des binären Baums in der Java -Programmierung. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!