Satélite

Instruções

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

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

Um percurso em pré-ordem lê o valor do nó atual antes (daí o "pré") de ler a subárvore esquerda em pré-ordem. A seguir, 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 em 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

Nota: o primeiro item do percurso em pré-ordem é sempre a raiz.