24 de Março
Travessia em níveis da árvore binária
Como percorrer uma árvore nivel por nivel usando fila e separar claramente o que pertence ao nivel atual antes de descer.
Árvores Intermediario 18 min TypeScript
Dada a raiz de uma árvore binaria, retorne seus valores nivel por nivel.
O resultado deve ser um array de arrays, onde cada array interno contem os valores de um nivel da árvore.
Exemplo:
Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
O que perceber antes de codar
- O problema pede agrupar por nivel.
- [`Busca em largura (BFS)`](/pt-br/glossario/bfs) visita a árvore em largura, que e exatamente a estrutura do resultado.
- A [`fila`](/pt-br/glossario/queue) precisa saber onde termina o nivel atual.
Erros comuns
- jogar todos os valores em um array único
- iterar sobre a fila enquanto ela cresce e misturar dois niveis no mesmo grupo
Passo 1 - Ler o formato da resposta com calma
O resultado não pede só percorrer a árvore.
Ele pede:
- separar por nivel
Isso já e uma pista forte de busca em largura (BFS).
Passo 2 - Escrever uma versão inicial que agrupa por profundidade
Uma versão inicial valida e busca em profundidade (DFS) com parametro level:
- quando entra num no, adiciona o valor em
result[level] - chama esquerda e direita com
level + 1
Funciona, mas a ideia de nivel fica mais indireta.
Passo 3 - Perceber por que busca em largura (BFS) combina melhor
- a fila guarda a fronteira da exploração
- os nos entram na ordem em que os niveis aparecem
Ou seja, a própria estratégia de percurso já tem o mesmo formato da resposta.
Passo 4 - Delimitar o nivel atual
O detalhe importante e:
- antes de processar um nivel, guarde
queue.length
Esse número diz quantos nos pertencem ao nivel atual.
Os filhos que entrarem durante o loop pertencem ao próximo nivel.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function levelOrder(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(n)
Solução 1 - Busca em profundidade (DFS) agrupando por profundidade
Boa versão inicial porque entrega o formato correto e reforca a ideia de profundidade.
export function levelOrder(root) {
const result = []
function dfs(node, level) {
if (node === null) {
return
}
if (!result[level]) {
result[level] = []
}
result[level].push(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
}
dfs(root, 0)
return result
}Funciona. Mas a fila da busca em largura (BFS) deixa a ideia de camada bem mais explicita.
Solução 2 - Busca em largura (BFS) por nivel com fila
Agora o percurso combina naturalmente com o resultado pedido.
export function levelOrder(root) {
if (root === null) {
return []
}
const result = []
const queue = [root]
while (queue.length > 0) {
const levelSize = queue.length
const level = []
for (let index = 0; index < levelSize; index += 1) {
const node = queue.shift()
level.push(node.val)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
result.push(level)
}
return result
}O ponto mais importante aqui e a fronteira do nivel atual.
O que dizer na entrevista
Uma explicação curta e boa seria:
Como a resposta pede grupos por nivel,
busca em largura (BFS)encaixa naturalmente. Eu uso umafilae, antes de processar cada camada, guardo o tamanho atual da fila. Esse tamanho me diz quantos nos pertencem ao nivel atual. Os filhos entram depois e ficam para a proxima rodada.
Isso mostra que você:
- leu o formato da resposta como pista de algoritmo
- entende a ideia de fronteira em
busca em largura (BFS) - sabe explicar por que os niveis não se misturam
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- percorrer árvore por camadas
- agrupar por nivel
- usar
filapara explorar largura - resolver zigzag, right side view e medias por nivel
O ponto não e decorar esse problema.
O ponto e perceber quando o formato da saída praticamente escolhe o algoritmo.