Alberi

Per gli scopi di questo esercizio, un albero è un albero binario con radice in cui tutti i nodi che non sono foglie hanno esattamente due figli e in cui tutti i nodi (comprese le foglie) sono etichettati con numeri interi non negativi.
Più precisamente, un albero con N nodi avrà i nodi etichettati con i numeri da 1 a N, e nodi diversi hanno etichette diverse.

Esistono tre modi standard per enumerare le etichette dei nodi di un albero, chiamati visita anticipata, simmetrica e posticipata.

La versione ricorsiva (in pseudocodice) delle tre visite è la seguente:

Ad esempio, considerate il seguente albero:
oii_2003_alberiEsempio di albero
Le tre visite applicate all’albero danno i seguenti risultati:
  • Visita anticipata: 5 3 2 1 6 7 4
  • Visita simmetrica: 2 3 6 1 7 5 4
  • Visita posticipata: 2 6 7 1 3 4 5

Il problema che dovete risolvere è il seguente: date le visite anticipata e posticipata, trovare la visita simmetrica.

Dati in input

Il file di input, di nome input.txt, contiene sulla prima riga un intero, il numero N di nodi dell’albero.
Seguono due righe, ciascuna delle quale contiene esattamente N numeri interi separati da uno spazio.
La prima delle due contiene la visita anticipata, la seconda contiene la visita posticipata.
Notate che i numeri che compaiono su ciascuna delle due righe sono compresi fra 1 e N e, ovviamente, su ogni riga ciascun numero compare esattamente una volta.

Dati in output

Il file di output, di nome output.txt, deve contenere una singola riga con N interi separati da spazi (eventuali spazi in eccesso saranno ignorati).
La riga deve corrispondere alla visita simmetrica dell’albero.

Assunzioni

  1. Il tempo limite di esecuzione è fissato in 1 secondo.
  2. 1 ≤ N ≤ 100.000.

Esempio

input.txt output.txt
7
5 3 2 1 6 7 4
2 6 7 1 3 4 5
2 3 6 1 7 5 4
Notice: This work is licensed under a BY-NC-SA. Permalink: Alberi

Comments are closed.