590. N-ary Tree Postorder Traversa
Schwierigkeit:Einfach
Themen:Stack, Baum, Tiefensuche
Gegebene Wurzel eines n-fachen Baums, gib die Postorder-Durchquerung der Werte seiner Knoten zurück.
Die Nary-Tree-Eingabeserialisierung wird in der Durchquerung ihrer Ebenenreihenfolge dargestellt. Jede Gruppe von Kindern wird durch den Nullwert getrennt (siehe Beispiele)
Beispiel 1:
Beispiel 2:
Einschränkungen:
Weitere Informationen: Eine rekursive Lösung ist trivial. Könnten Sie sie iterativ durchführen?
Lösung:
Wir können es sowohl rekursiv als auch iterativ angehen. Da das Follow-up eine iterative Lösung erfordert, werden wir uns darauf konzentrieren. Postorder-Traversal bedeutet, zuerst die untergeordneten Knoten und dann den übergeordneten Knoten zu besuchen.
Lassen Sie uns diese Lösung in PHP implementieren: 590. N-ary Tree Postorder Traversal
val = $val;
}
}
/**
* @param Node $root
* @return integer[]
*/
function postorder($root) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example 1:
$root1 = new Node(1);
$root1->children = [
$node3 = new Node(3),
new Node(2),
new Node(4)
];
$node3->children = [
new Node(5),
new Node(6)
];
print_r(postorder($root1)); // Output: [5, 6, 3, 2, 4, 1]
// Example 2:
$root2 = new Node(1);
$root2->children = [
new Node(2),
$node3 = new Node(3),
$node4 = new Node(4),
$node5 = new Node(5)
];
$node3->children = [
$node6 = new Node(6),
$node7 = new Node(7)
];
$node4->children = [
$node8 = new Node(8)
];
$node5->children = [
$node9 = new Node(9),
$node10 = new Node(10)
];
$node7->children = [
new Node(11)
];
$node8->children = [
new Node(12)
];
$node9->children = [
new Node(13)
];
$node11 = $node7->children[0];
$node11->children = [
new Node(14)
];
print_r(postorder($root2)); // Output: [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]
?>
Erläuterung:
-
Initialisierung:
- Erstellen Sie einen Stapel und schieben Sie den Wurzelknoten darauf.
- Erstellen Sie ein leeres Array-Ergebnis, um den endgültigen Postorder-Durchlauf zu speichern.
-
Durchquerung:
- Entfernen Sie den Knoten vom Stapel und fügen Sie seinen Wert am Anfang des Ergebnisarrays ein.
- Schiebt alle seine untergeordneten Elemente auf den Stapel.
- Fahren Sie fort, bis der Stapel leer ist.
-
Ergebnis:
- Das Ergebnisarray enthält die Knoten in der Nachfolge, nachdem die Schleife beendet ist.
Dieser iterative Ansatz simuliert effektiv die Postorder-Traversierung, indem er einen Stapel verwendet und den normalerweise durch Rekursion durchgeführten Prozess umkehrt.
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:
Das obige ist der detaillierte Inhalt von. N-ary Tree Mail Order Traverse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
