. Binärbaum-Postorder-Traversal

145. Binärbaum-Postorder-Traversal

Schwierigkeit:Einfach

Themen: Stapel, Baum, Tiefensuche, Binärbaum

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

Beispiel 1:

• 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: Links, Rechts, Wurzel.

Lassen Sie uns diese Lösung in PHP implementieren: 145. Binärbaum-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, bis 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, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre 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!