. Binärbaum-Postorder-Traversal-PHP-Tutorial-php.cn

145. Binärbaum-Postorder-Traversal

Schwierigkeit:Einfach

Themen:Stapel, Baum, Tiefensuche, Binärbaum

Gibt bei gegebener Wurzel eines Binärbaumsdie Postorder-Durchquerung der Werte seiner Knoten zurück.

Beispiel 1:

. Binary Tree Postorder Traversal

Eingabe:root = [1,null,2,3]
Ausgabe:[3,2,1]

Beispiel 2:

Eingabe:root = []
Ausgabe:[]

Beispiel 3:

Eingabe:root = [1]
Ausgabe:[1]

Einschränkungen:

Die Anzahl der Knoten im Baum liegt im Bereich [0, 100].
-100 <= Node.val <= 100

Lösung:

Wir können einen iterativen Ansatz mit einem Stapel verwenden. Postorder-Traversal folgt der Reihenfolge: Left, Right, Root.

Lassen Sie uns diese Lösung in PHP implementieren:145. Binary Tree Postorder Traversal

        val = $val; $this->left = $left; $this->right = $right; } } /** * @param TreeNode $root * @return Integer[] */ function postorderTraversal($root) { ... ... ... /** * go to ./solution.php */ } // Example usage: // Example 1 $root1 = new TreeNode(1); $root1->right = new TreeNode(2); $root1->right->left = new TreeNode(3); print_r(postorderTraversal($root1)); // Output: [3, 2, 1] // Example 2 $root2 = null; print_r(postorderTraversal($root2)); // Output: [] // Example 3 $root3 = new TreeNode(1); print_r(postorderTraversal($root3)); // Output: [1] ?>Erläuterung:
        
         TreeNode-Klasse:Die TreeNode-Klasse definiert einen Knoten im Binärbaum, einschließlich seines Werts, seines linken und rechten untergeordneten Knotens.
         postorderTraversal-Funktion:
          
           Wir initialisieren ein leeres Ergebnisarray und einen Stapel.
           Wir verwenden eine While-Schleife, die so lange andauert, wie entweder der Stapel nicht leer ist oder der aktuelle Knoten nicht null ist.
           Wenn der aktuelle Knoten nicht null ist, schieben wir ihn auf den Stapel und verschieben ihn zu seinem linken untergeordneten Knoten.
           Wenn der aktuelle Knoten null ist, überprüfen wir den obersten Knoten des Stapels. Wenn es ein richtiges Kind gibt, das wir noch nicht besucht haben, wechseln wir zum richtigen Kind. Andernfalls fügen wir den Wert des Knotens zum Ergebnisarray hinzu und entfernen ihn vom Stapel.
          
        
Dieser iterative Ansatz simuliert den rekursiven Postorder-Durchlauf ohne Verwendung einer Systemrekursion und macht ihn dadurch speichereffizienter.
Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, demRepositoryeinen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Eure Unterstützung würde mir sehr viel bedeuten!
Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:
        
         LinkedIn
         GitHub
        
Das obige ist der detaillierte Inhalt von. Binärbaum-Postorder-Traversal. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!