De-reconstrucción
En los árboles binarios hay tres recorridos fundamentales: los recorridos en preorden, inorden y postorden. Todos ellos generan una lista que contiene todos los elementos almacenados en el árbol en un orden que varía dependiendo del recorrido. En los casos fáciles los tres recorridos coinciden: el recorrido del árbol vacío es la lista vacía y en el recorrido de un árbol con un único nodo, la lista tiene ese elemento.
Cuando los árboles tienen más de un nodo, el recorrido es el siguiente:
- En el recorrido en preorden, el primer elemento de la lista es el contenido de la raíz. A continuación vienen los recorridos en preorden del hijo izquierdo y luego del derecho.
- En el recorrido en inorden aparece primero el recorrido en inorden del hijo izquierdo, después el elemento almacenado en la raíz, y por último el recorrido en inorden del hijo derecho.
- En el recorrido en postorden aparecen primero los recorridos de ambos hijos y finalmente el elemento almacenado en la raíz.
Si se piensa un poco, es fácil ver que dos árboles distintos pueden tener el mismo recorrido en inorden, por ejemplo. Eso significa que dado un recorrido en inorden no es posible reconstruir el árbol original, pues éste no es único.
Sin embargo, si los elementos almacenados en el árbol no están repetidos, es posible reconstruirlo a partir de los recorridos en preorden e inorden.
Entrada
La entrada consistirá en distintos casos de prueba, cada uno de ellos ocupando dos líneas. Las dos líneas contienen el recorrido en preorden e inorden de un árbol de enteros positivos cuyos valores no están repetidos. Ambas listas de números terminan con -1. Se garantiza que el árbol no tendrá más de 2.000 nodos.
Los casos de prueba terminarán con un recorrido en preorden vacío, es decir, con un -1.
Salida
Para cada caso de prueba se escribirá el recorrido en postorden del árbol.
Entrada de ejemplo
1 -1 1 -1 2 1 0 -1 0 1 2 -1 1 0 2 -1 0 1 2 -1 -1
Salida de ejemplo
1 0 1 2 0 2 1