Post-Order-Traversierung eines Binärbaums
Die Post-Order-Traversierung eines Baums ist ein rekursives Verfahren, bei dem man zuerst den linken Teilbaum eines Knotens besucht, anschließend den rechten Teilbaum und schließlich den Knoten selbst:
- Den linken Teilbaum besuchen (
node.left)
- Den rechten Teilbaum besuchen (
node.right)
- Den aktuellen Knoten besuchen
Angenommen, du hast einen Binärbaum. Deine Aufgabe besteht darin, eine Post-Order-Traversierung auf diesem Baum durchzuführen.
Eingabe
Die Eingabe enthält durch Leerzeichen getrennte ganze Zahlen, die die Werte in den Knoten des Binärbaums repräsentieren. Die Reihenfolge der Werte wird immer durch das Durchlaufen vom linken zum rechten Teilbaum bestimmt. Ein Wert von 0 bedeutet, dass der entsprechende Knoten nicht existiert. Es ist sichergestellt, dass der übergebene Binärbaum gültig ist.
Ausgabe
Das Programm soll die Werte aus den Knoten in der Reihenfolge einer Post-Order-Traversierung ausgeben. Alle Werte sollen durch ein Leerzeichen voneinander getrennt sein.
Beispiele
Eingabe | Ausgabe |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 9 4 5 2 6 7 3 1 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 5 2 6 7 3 1 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 5 2 6 8 9 7 3 1 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 7 8 5 2 6 3 1 |
Erklärung
- Beispiel 1:
.png?table=block&id=18a2c681-664d-81bb-825f-c72cb526dfa4&cache=v2)
- Beispiel 2:
.png?table=block&id=18a2c681-664d-81e8-9b86-e1abeaca5b55&cache=v2)
- Beispiel 3:
.png?table=block&id=18a2c681-664d-8104-91e4-cb4c2e5ac850&cache=v2)
- Beispiel 4:
.png?table=block&id=18a2c681-664d-8121-91d4-d1625162f1c2&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB