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

Salida

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