En l’exercici es descriu un arbre binari de cerca amb el seu recorregut en preordre, el qual inclou un -1 per a cada fulla. Però, de fet, no cal incloure els -1’s en el preordre d’un arbre de cerca per poder reconstruir-lo.
Feu un programa que llegeixi una seqüència d’arbres binaris de cerca descrits amb els seus recorreguts en preordre sense -1’s. Per a cada arbre, cal escriure el seu recorregut en postordre.
Entrada
L’entrada consisteix en una seqüència de descripcions d’arbres binaris segons s’explica a l’exercici , amb una excepció: S’ometen els -1’s corresponents a les fulles. Suposeu que els arbres són de cerca i que els seus elements són naturals.
Sortida
Per a cada arbre de l’entrada, escriviu una línia amb el recorregut en postordre de l’arbre. Cada element ha de sortir precedit d’un espai.
Input
10 180 155 60 80 170 300 240 400 310 340 3 30 20 10
Output
80 60 170 155 240 340 310 400 300 180 10 20 30