Problema número 280

Recorridos de un árbol triangular aplastado

Tiempo máximo: 1,000-4,000 sMemoria máxima: 8192 KiB

Cuando un árbol binario no tiene elementos repetidos, es posible reconstruir su estructura completa a partir de, por ejemplo, el recorrido en preorden y en inorden. Sin embargo, si en lugar de darnos los dos recorridos nos dan únicamente uno, esta reconstrucción no es posible a no ser que nos den información adicional sobre el árbol original.

En este caso haremos precisamente eso. Debemos reconstruir un árbol binario a partir de únicamente su recorrido en inorden sabiendo que el árbol original era triangular ligeramente inclinado a la izquierda. Un árbol es así cuando cualquier subárbol cumple la siguiente condición: su hijo izquierdo tiene el mismo número de nodos que su hijo derecho, o como mucho un nodo más. Por ejemplo, el siguiente árbol es triangular:

Un árbol triangular ligeramente inclinado a la izquierda

Entrada

Cada caso de prueba consiste en una única línea de números no negativos terminados con un -1. La lista de números representa el recorrido en inorden del árbol triangular que hay que reconstruir (la altura será como mucho 14). Ten en cuenta que el recorrido no incluye el -1.

La entrada terminará con un recorrido en inorden vacío, que no generará salida.

Salida

Para cada caso de prueba se escribirán dos líneas, una con el recorrido en preorden y otra con el recorrido en postorden del árbol original.

Entrada de ejemplo

1 2 3 4 -1
1 2 3 4 5 -1
1 2 3 4 5 6 7 8 9 10 -1
-1

Salida de ejemplo

3 2 1 4
1 2 4 3
3 2 1 5 4
1 2 4 5 3
6 3 2 1 5 4 9 8 7 10
1 2 4 5 3 7 8 10 9 6