Recorridos de un árbol triangular aplastado
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:
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