Padrão 4: Construção e serialização
Até aqui consumimos árvores prontas. Agora o problema inverso: construir uma árvore (a partir de travessias ou de uma string) sem ambiguidade. É recursão de novo — mas a sacada está em entender o que cada travessia revela.
Tente primeiro: Construct Binary Tree from Preorder and Inorder
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Reconstrua a árvore binária a partir das suas travessias pré-ordem e em-ordem (sem valores repetidos). Retorne a raiz.
Exemplo: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → [3,9,20,null,null,15,7].
Tentou? O desafio é descobrir, a cada passo, quem é a raiz e onde a árvore se divide em esquerda e direita. A teoria abaixo mostra como pré-ordem e em-ordem, juntas, dão essa informação.
A teoria 1: reconstruir a partir de travessias
Uma única travessia não basta para reconstruir a árvore (várias árvores diferentes dão a mesma pré-ordem). Mas pré-ordem + em-ordem juntas determinam a árvore de forma única. A chave são duas observações:
- Pré-ordem (nó → esq → dir): o primeiro elemento é sempre a raiz.
- Em-ordem (esq → nó → dir): a raiz divide a lista — tudo à esquerda dela é a subárvore esquerda, tudo à direita é a direita.
pré: [3, 9, 20, 15, 7] → raiz é 3
em: [9, 3, 15, 20, 7] → 9 | 3 | 15,20,7
↑esq ↑raiz ↑dir
Então: pegue a raiz da pré-ordem, ache-a na em-ordem para saber o tamanho de
cada lado, e recursivamente construa esquerda e direita. Consuma a
pré-ordem com um ponteiro que só avança (ela já está na ordem certa: raiz, toda
a esquerda, toda a direita). Um mapa valor → posição na em-ordem evita buscas
e mantém O(n).
A teoria 2: serializar e desserializar
Serializar é transformar a árvore numa string; desserializar é reconstruí-la exatamente. É o mesmo problema de representação sem ambiguidade que você viu em String (codificação) — agora aplicado à estrutura da árvore.
A forma mais limpa: pré-ordem com marcadores de vazio. Escreva o valor do
nó e, para cada filho ausente, um marcador (#). Isso registra a estrutura
completa, então a reconstrução é única:
1
/ \ → serializa (pré-ordem) → "1,2,#,#,3,#,#"
2 3
Na volta, leia os tokens em ordem: um valor cria um nó (e recursivamente lê
seus dois filhos); um # é None. Como a pré-ordem coloca cada nó antes
dos filhos, ler na mesma ordem reconstrói perfeitamente.
Complexidade
Ambas as direções visitam cada nó (e cada marcador de vazio) uma vez → O(n) de tempo. A serialização produz uma string O(n); a desserialização usa a pilha de recursão O(h). O ponteiro de leitura nunca volta — cada token é consumido uma vez.
A lição que conecta as seções
Construir a partir de travessias e serializar são variações de uma ideia: a ordem em que você grava/lê os nós precisa carregar a estrutura sem ambiguidade. A pré-ordem resolve isso porque coloca a raiz antes dos filhos. É o mesmo princípio do length-prefix da seção String — representar dados de forma reconstruível. Padrões viajam entre seções.
🧠 Quiz de fixação
0/41. Por que uma única travessia (só pré-ordem, por exemplo) não basta para reconstruir a árvore?
2. Na reconstrução com pré + em-ordem, o que cada travessia fornece?
3. Por que a serialização em pré-ordem COM marcadores de vazio (#) reconstrói a árvore sem ambiguidade?
4. Que princípio de outra seção a serialização de árvore reaproveita?
Resumo
- Reconstruir de pré + em-ordem: pré dá a raiz; em-ordem divide esquerda/direita; recursão monta. O(n).
- Serializar: pré-ordem com marcadores de vazio (
#) registra a estrutura sem ambiguidade; desserializar lê na mesma ordem. - Mesmo princípio do length-prefix da seção String: representação reconstruível.
Próxima aula: uma árvore especializada em texto — a Trie.