Algoritmi e Strutture Dati

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:
  1. Visitare il sottoalbero sinistro (node.left)
  1. Visitare il sottoalbero destro (node.right)
  1. 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

  1. Esempio 1:
      2. notion image
  1. Esempio 2:
      2. notion image
  1. Esempio 3:
      2. notion image
  1. Esempio 4:
      2. notion image
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue