. N-ary Tree Mail Order Traverse

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:

• Eingabe: root = [1,null,3,2,4,null,5,6]
• Ausgabe: [5,6,3,2,4,1]

Beispiel 2:

• Eingabe: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12 ,null,13,null,null,14]
• Ausgabe: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Einschränkungen:

• Die Anzahl der Knoten im Baum liegt im Bereich [0, 100⁴].
• -100 <= Node.val <= 100⁴
• Die Höhe des n-fachen Baums ist kleiner oder gleich 1000.

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:


LinkedIn
GitHub



          

            
  

            
        
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!