Visita in-order di un albero binario
La visita in-order di un albero è una procedura ricorsiva, in cui si visita prima il sottoalbero sinistro di un nodo, poi il nodo stesso e infine il suo sottoalbero destro:
Visit the left subtree (
node.left)Visit the current node
Visit the right subtree (
node.right)
È come se l’albero binario fosse sospeso dalla radice e si leggessero i suoi valori da sinistra a destra.
Dato un albero binario, il compito è quello di eseguire una visita in-order su di esso.
Input
L’input consiste in numeri interi separati da spazi, che rappresentano i valori memorizzati nei nodi dell’albero binario. L’ordine dei valori segue una traversata che va prima nel sottoalbero sinistro e poi in quello destro ogni volta. Un valore pari a 0 indica che il nodo non esiste. È garantito che l’albero binario fornito in ingresso sia valido.
Output
Il programma deve stampare i valori dei nodi di un albero binario durante la visita in-order, separando ciascun valore con uno spazio.
Esempi
Dati in ingresso | Dati in uscita |
|---|---|
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 4 9 2 5 1 6 3 7 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 2 5 1 6 3 7 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 2 5 1 6 3 8 7 9 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 2 7 5 8 1 3 6 |
Spiegazione
Esempio 1:
Esempio 2:
Esempio 3:
Esempio 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB