Padrão 1: DFS recursivo
Este é o padrão que resolve a maioria dos problemas de árvore. A ideia é contraintuitiva no começo: você não percorre a árvore "na mão" — você confia na recursão para resolver as subárvores e só decide como combinar.
Tente primeiro: Maximum Depth of Binary Tree
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.
Retorne a profundidade máxima de uma árvore binária (número de nós no caminho mais longo da raiz até uma folha). A árvore é dada como root (cada nó tem .val, .left, .right).
Exemplo: [3,9,20,null,null,15,7] → 3. (Para testar, passamos a árvore em ordem de nível.)
Tentou? Se você tentou percorrer nível a nível contando, funciona — mas há uma forma muito mais simples e direta de pensar. A teoria abaixo mostra o "salto de fé" recursivo.
A teoria: o salto de fé recursivo
Diante de uma árvore, em vez de imaginar todos os nós, faça três perguntas:
- Caso-base: qual a resposta para a árvore vazia (
None)? (quase sempre o trivial: 0,True,None...) - Salto de fé: assuma que a recursão já te deu a resposta correta para a subárvore esquerda e para a direita.
- Combinar: como montar a resposta do nó atual a partir dessas duas respostas?
Esse é o template universal de DFS em árvore:
def resolve(no):
se no é None: → retorna o caso-base
esq = resolve(no.left) # salto de fé
dir = resolve(no.right) # salto de fé
return combinar(no, esq, dir)
Para o Maximum Depth: caso-base None → 0; combinação
1 + max(esquerda, direita). Você nunca pensa na árvore inteira — só no nó
atual confiando nos filhos. Veja o DFS descer até o fundo e voltar combinando
(o azul mostra os nós já visitados, o âmbar é onde a recursão está agora):
Por que é O(n) tempo e O(h) espaço?
A função é chamada uma vez por nó (cada nó é o "no" de exatamente uma chamada) e faz trabalho O(1) para combinar → O(n) de tempo. O espaço é a profundidade da pilha de recursão, que vai até a altura h: O(h) — log n se balanceada, n no pior caso (lembra da aula anterior).
O mesmo template, outros problemas
Trocando só a combinação e o caso-base, o template resolve uma família inteira:
| Problema | Caso-base | Combinar |
|---|---|---|
| Profundidade máxima | None → 0 | 1 + max(esq, dir) |
| Inverter a árvore | None → None | troca: no.left=dir; no.right=esq |
| São iguais? (duas árvores) | ambas None → True | a.val==b.val E esq E dir |
| Soma de todos os valores | None → 0 | no.val + esq + dir |
Veja inverter e são iguais — repare que só muda a linha do combinar:
A virada de chave
O que separa quem sofre com árvores de quem resolve: parar de tentar "seguir os ponteiros na cabeça" e passar a confiar na recursão. Defina o caso-base, assuma que os filhos estão resolvidos, e foque só na combinação. Esse hábito mental vale para árvores, e depois para grafos e DP.
🧠 Quiz de fixação
0/41. Qual é o 'template universal' de DFS recursivo em árvore?
2. Para a profundidade máxima, qual a combinação correta a partir das respostas dos filhos?
3. Por que o DFS recursivo em árvore é O(n) de tempo?
4. Inverter a árvore e checar se duas árvores são iguais usam o MESMO template. O que muda entre eles?
Resumo
- Template universal: caso-base (None) → resolve(esq) → resolve(dir) → combinar.
- "Salto de fé": confie que a recursão resolve os filhos; foque na combinação.
- O(n) tempo, O(h) espaço (pilha de recursão).
- Profundidade, inverter, igualdade, soma... todos são o mesmo template.
Próxima aula: quando a pergunta é por nível — BFS.