Síntese: qual padrão usar?
Cinco padrões de árvore cobertos. Hora de treinar o reflexo: ler um problema de árvore e saber qual ferramenta sacar — com justificativa.
A árvore de decisão da seção
1. A resposta se COMBINA a partir das subárvores (altura, soma, validar, inverter)?
→ DFS RECURSIVO (caso-base None → resolve esq → resolve dir → combinar)
2. A pergunta é por NÍVEL (valores de cada nível, vista lateral, profundidade mínima)?
→ BFS por níveis (fila + truque do tamanho do nível)
3. É uma BST (esquerda < nó < direita)?
├── buscar / LCA / inserir → desce só por um lado: O(h)
└── "k-ésimo menor" / ordenado → travessia EM-ORDEM (crescente)
4. Preciso RECONSTRUIR ou SERIALIZAR a árvore?
→ pré-ordem dá a raiz; marcadores de vazio tornam a string reconstruível
5. O problema é sobre PREFIXOS ou um dicionário de palavras?
→ TRIE (caminho por caractere; O(L) por operação)
E o reflexo que vale a seção inteira: pense recursivamente. Defina o caso-base, confie que a recursão resolve os filhos, e foque na combinação. A maioria das árvores cede a esse hábito.
O mapa completo da seção
| Padrão | Pergunta-chave | Tempo | Espaço |
|---|---|---|---|
| DFS recursivo | "combinar resultado dos filhos" | O(n) | O(h) |
| BFS por níveis | "por nível / menor profundidade" | O(n) | O(largura) |
| BST (busca/LCA) | "esquerda < nó < direita" | O(h) | O(h) |
| BST em-ordem | "k-ésimo / ordenado" | O(n) | O(h) |
| Construção/serialização | "reconstruir sem ambiguidade" | O(n) | O(h) |
| Trie | "prefixos / dicionário" | O(L) por op. | O(total de chars) |
Repare no O(h) recorrente: a altura governa o espaço da recursão e o tempo da busca em BST. Balanceada → log n; degenerada → n. Esse é o aprofundamento de Big-O desta seção — sempre que disser O(h), saiba o que h significa.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 7+ acertos: pronto para a prova.
🧠 Quiz da seção: Árvores
0/81. 'Some todos os valores da árvore.' Qual padrão e qual a combinação?
2. 'Qual a profundidade MÍNIMA (até a folha mais rasa)?' Por que BFS é uma ótima escolha?
3. 'Numa BST, encontre o sucessor em-ordem de um valor.' Que propriedade ajuda?
4. 'Verifique se uma árvore é espelhada em torno do centro (simétrica).' Qual padrão?
5. 'Autocompletar: dadas muitas palavras, responder rápido se um prefixo existe.' Qual estrutura?
6. 'Maior soma de caminho na árvore (pode virar num nó, valores negativos).' Por que é DFS com cuidado?
7. Por que tantos algoritmos de árvore têm espaço O(h) em vez de O(n)?
8. Qual a ideia-mãe que une quase toda a seção de Árvores?
Pronto para a prova?
A prova final da seção Árvores tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil (maior soma de caminho) é DFS recursivo com a sutileza de separar "o que retorno para o pai" de "a melhor resposta que posso formar aqui". As cinco aulas cobrem tudo que você precisa.
Boa prova! Volte para a página da seção e clique em "Prova final".