Padrão 2: BFS por níveis
A recursão (DFS) vai fundo num ramo antes de voltar. Mas algumas perguntas são sobre níveis — "os valores de cada nível", "o nó mais à direita de cada linha", "a profundidade mínima". Para essas, a busca em largura (BFS), com uma fila, processa a árvore camada por camada.
Tente primeiro: Binary Tree Level Order Traversal
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 os valores da árvore nível por nível, de cima para baixo, da esquerda para a direita — uma lista por nível.
Exemplo: [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]].
Tentou? Com DFS dá para fazer (guardando a profundidade de cada valor), mas separar os níveis fica desajeitado. A teoria abaixo mostra o jeito limpo: processar a fila "um nível de cada vez".
A teoria: a fila e o truque do tamanho do nível
A BFS usa uma fila (FIFO): você enfileira a raiz e, repetidamente, tira o nó da frente e enfileira seus filhos. Isso visita os nós em ordem de nível (raiz, depois nível 1, depois nível 2...). Veja a fila avançando nível a nível (o âmbar é o nó sendo processado, o azul os já visitados):
Mas como separar os níveis em listas distintas? O truque é simples e elegante: no início de cada rodada, a fila contém exatamente um nível inteiro. Então capture o tamanho atual da fila e processe só esse tanto de nós — eles são o nível atual; os filhos que você enfileira formarão o próximo:
fila = [raiz]
enquanto a fila não está vazia:
tamanho = len(fila) # ← congela o nível atual
nivel = []
repita `tamanho` vezes:
no = desenfileira
nivel.append(no.val)
enfileira no.left e no.right (se existirem)
resultado.append(nivel)
Por que é O(n) tempo e O(n) espaço?
Cada nó entra e sai da fila exatamente uma vez → O(n) de tempo. O espaço é o tamanho máximo da fila, que é a largura da árvore — no pior caso (o último nível de uma árvore cheia) é ~n/2 nós → O(n) de espaço. Note o contraste com o DFS: lá o espaço era O(h) (altura); aqui é O(largura).
DFS ou BFS numa árvore?
| A pergunta é sobre... | Use | Por quê |
|---|---|---|
| propriedade que se combina dos filhos (altura, soma, validar) | DFS recursivo | a recursão combina naturalmente |
| níveis (por nível, nível mais profundo, vista lateral) | BFS | a fila processa camada a camada |
| menor profundidade / "menos passos" até algo | BFS | acha o nível raso primeiro |
Curiosidade que conecta com Matriz: este é o mesmo BFS que você usou no grid para o caminho mais curto. Árvore e grid são grafos; BFS por camadas é o mesmo algoritmo. Você está praticando grafos sem perceber.
🧠 Quiz de fixação
0/41. Qual estrutura de dados a BFS usa, e em que ordem ela visita os nós?
2. Como separar os níveis em listas distintas durante a BFS?
3. Qual a complexidade de espaço da BFS numa árvore, e por quê?
4. 'Retorne a vista do lado direito da árvore (o nó mais à direita de cada nível).' Qual padrão?
Resumo
- BFS usa uma fila e visita a árvore nível por nível.
- Separe níveis capturando o tamanho da fila no início de cada rodada.
- O(n) tempo; O(n) espaço (largura) — contraste com O(h) do DFS.
- Use BFS para perguntas por nível ou de menor profundidade.
Próxima aula: a árvore com uma regra de ouro que dá busca rápida — a BST.