Percorra árvores de forma recursiva
Resolva problemas de árvore binária combinando as respostas das subárvores.
- Escrever funções recursivas de árvore com um caso base claro.
- Comparar os percursos pré-ordem, em ordem, pós-ordem e por nível.
- Usar a propriedade da árvore binária de busca.
Um nó de árvore binária tem um valor e até dois filhos. A maioria dos problemas de árvore tem o mesmo formato: tratar a árvore vazia (o caso base), resolver o problema para as subárvores esquerda e direita de forma recursiva e depois combinar as respostas. A altura da árvore, se duas árvores são idênticas, a soma de um caminho - tudo segue esse padrão.
Percursos e a propriedade da BST
- Pré-ordem (nó, esquerda, direita): copiar ou serializar uma árvore.
- Em ordem (esquerda, nó, direita): visita uma árvore binária de busca em ordem crescente.
- Pós-ordem (esquerda, direita, nó): quando um nó precisa primeiro das respostas dos filhos, como na altura.
- Por nível (em largura, com uma fila): processar a árvore uma profundidade de cada vez.
Numa árvore binária de busca (BST), todo valor da subárvore esquerda de um nó é menor e todo valor da subárvore direita é maior, então buscar, inserir e remover levam O(h), em que h é a altura.
1class TreeNode:
2 def __init__(self, value, left=None, right=None):
3 self.value = value
4 self.left = left
5 self.right = right
6
7def max_depth(node):
8 if node is None:
9 return 0
10 return 1 + max(max_depth(node.left), max_depth(node.right))
11
12# 3
13# / \
14# 9 20
15# / \
16# 15 7
17root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
18print(max_depth(root))3
As soluções recursivas de árvore visitam cada nó uma vez, então são O(n) de tempo. O espaço delas é O(h) por causa da pilha de chamadas: O(log n) para uma árvore balanceada, mas O(n) para uma árvore que degenera numa linha. Se o entrevistador se preocupar com recursão profunda, converta para uma pilha explícita ou para uma fila de BFS.
Principais conclusões
Caso base para árvores vazias, recursão nos filhos, combinação.
O percurso em ordem de uma BST sai ordenado.
A recursão usa O(h) de espaço na pilha.
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Meça a profundidade de uma árvore
Leia uma árvore binária por nível, com null para os filhos ausentes (por exemplo, 3 9 20 null null 15 7). O código inicial monta a árvore. Imprima a profundidade máxima dela; uma linha vazia significa uma árvore vazia, com profundidade 0.
- Árvore de exemplo
- Inclinada para a esquerda
- Árvore vazia
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…