Visita in post-ordine di un albero binario
La visita in post-ordine (post-order traversal) di un albero è una procedura ricorsiva in cui per ogni nodo si visita prima il sottoalbero sinistro, poi il sottoalbero destro e infine il nodo stesso:
Visitare il sottoalbero sinistro (
node.left)Visitare il sottoalbero destro (
node.right)Visitare il nodo corrente
Dato un albero binario, il tuo compito è eseguirne la visita in post-ordine.
Dati in ingresso
L’input contiene interi separati da spazi che rappresentano i valori dei nodi dell’albero binario. L’ordine dei valori è determinato passando sempre dal sottoalbero sinistro a quello destro. Un valore di 0 indica che il nodo non esiste. È garantito che l’albero binario fornito come input sia valido.
Output
Il programma deve stampare i valori dei nodi dell’albero binario seguendo la visita in post-ordine, separandoli tutti con uno spazio.
Esempi
Input | Output |
|---|---|
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 |
Spiegazione
Esempio 1:
Esempio 2:
Esempio 3:
Esempio 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB