Ir al contenido (saltar navegación)

Ductilidad de los árboles binarios

Tiempo máximo: 1,000-3,000 sMemoria máxima: 4096 KiB

La maleabilidad es la propiedad de un material sólido de adquirir una deformación mediante una compresión sin fracturarse; cuando un material es maleable se pueden hacer láminas muy finas con él. De forma similar, la ductilidad es otra propiedad que, en vez de láminas, permite hacer alambres o hilos muy finos.

Los árboles binarios están hechos de un material muy dúctil, que nos permite estirar el árbol en un hilo muy fino, de tan solo un elemento de grosor. Dependiendo del tipo de manipulación utilizada para conseguir el hilo, los átomos (nodos) originales del árbol (que contienen sus elementos) quedan colocados de formas distintas. Hay cuatro formas de manipulación básicas: la obtención por el mecanismo de preorden, de inorden, de postorden y de niveles.

Un buen joyero de árboles es capaz de recuperar el árbol original a partir de dos finos cables sacados de dos árboles iguales. ¿Eres un buen joyero?

Entrada

La entrada consistirá en distintos casos de prueba, cada uno de ellos ocupando tres líneas. La primera línea contiene el número N de nodos del árbol original. A continuación vienen dos líneas cada una con N enteros positivos, que se corresponden con el recorrido del árbol en inorden y postorden respectivamente. Se garantiza que el árbol original (y por tanto los recorridos dados) no tiene valores repetidos.

La entrada termina con una línea con un 0.

Salida

Para cada caso de prueba se escribirá el recorrido en preorden del árbol. Se garantiza que el árbol no tendrá más de 1.000 nodos.

Entrada de ejemplo

1
1
1
3
0 1 2
0 1 2
3
0 1 2
0 2 1
0

Salida de ejemplo

1
2 1 0
1 0 2