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.

Mensagens de exceção

Às vezes é necessário lançar uma exceção. Quando você faz isso, deve sempre incluir uma mensagem de erro significativa para indicar qual é a origem do erro. Isso deixa seu código mais legível e ajuda muito na depuração. Em situações em que você sabe que a origem do erro será de um tipo específico, você pode optar por lançar um dos tipos de erro embutidos, mas ainda assim deve incluir uma mensagem significativa.

Este exercício em particular exige que você use a instrução raise para "lançar" um ValueError se os argumentos preorder e inorder não tiverem o mesmo comprimento, não compartilharem os mesmos elementos ou se os elementos não forem únicos. Os testes só vão passar se você lançar a exception com raise e incluir uma mensagem junto com ela.

Para lançar um ValueError com uma mensagem, escreva a mensagem como um argumento do tipo exception:

# if preorder and inorder are not the same length
raise ValueError("traversals must have the same length")

# if preorder and inorder do not share the same elements
raise ValueError("traversals must have the same elements")
    
# if element repeat (are not unique)    
raise ValueError("traversals must contain unique items")