Satélite

Instruções

Imagine que você precisa transmitir uma árvore binária para um satélite que se aproxima de Alpha Centauri e tem largura de banda limitada. Como a árvore não tem itens repetidos, ela pode ser representada de forma única pelos seus percursos pré-ordem e em ordem.

Escreva o software do satélite para reconstruir a árvore a partir dos percursos.

Um percurso pré-ordem lê o valor do nó atual antes (daí o "pré") de ler a subárvore esquerda em pré-ordem. Em seguida, a subárvore direita é lida em pré-ordem.

Um percurso em ordem lê a subárvore esquerda em ordem, depois o nó atual e, por fim, a subárvore direita em ordem. Ou seja, da esquerda para a direita.

Por exemplo, o percurso pré-ordem desta árvore é [a, i, x, f, r]. O percurso em ordem desta árvore é [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Observação: o primeiro item do percurso pré-ordem é sempre a raiz.