24 de Março
Profundidade máxima de árvore binária
Como medir a altura de uma árvore pensando em folhas, subarvores e na combinação 1 + max(esquerda, direita).
Árvores Iniciante 10 min TypeScript
Dada a raiz de uma árvore binaria, retorne sua profundidade máxima.
A profundidade máxima e o número de nos no caminho mais longo da raiz até uma folha.
Exemplo:
Input: [3,9,20,null,null,15,7]
Output: 3
O que perceber antes de codar
- Árvore vazia devolve `0`.
- Folha devolve `1`, não `0`.
- O problema pede o caminho mais longo, entao você quer `max`, não `min`.
Erros comuns
- retornar `0` para folha e deslocar toda a resposta
- usar o menor lado em vez do maior
Passo 1 - Traduzir o enunciado para uma pergunta menor
"Profundidade máxima" parece abstrato no começo.
Mas a pergunta real e:
- quantos nos existem no caminho mais longo até uma folha?
Passo 2 - Escrever uma versão inicial que deixa isso visível
Uma versão inicial boa e percorrer a árvore por niveis com busca em largura (BFS):
- começa com a raiz
- processa um nivel inteiro
- incrementa a profundidade
Quando a fila acaba, você sabe quantos niveis existiam.
Passo 3 - Perceber a regra recursiva
Para qualquer no:
- a profundidade da esquerda e um subproblema
- a profundidade da direita e outro subproblema
- a resposta atual e
1 + max(...)
Esse e o centro do problema.
Passo 4 - Definir o caso base sem tropecar
Os casos base sao:
null-> profundidade0- folha ->
1, porque o no atual conta
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function maxDepth(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// sua solução aqui
return 0
}
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(h)
Solução 1 - Busca em largura (BFS) por niveis
Boa versão inicial porque deixa a ideia de “quantos andares existem” bem concreta.
export function maxDepth(root) {
if (root === null) {
return 0
}
const queue = [root]
let depth = 0
while (queue.length > 0) {
const levelSize = queue.length
depth += 1
for (let index = 0; index < levelSize; index += 1) {
const node = queue.shift()
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
}
return depth
}Funciona bem. Mas a recursao captura a definição do problema de forma mais direta.
Solução 2 - Busca em profundidade (DFS) recursiva com recursao
Agora a solução segue a própria definição de profundidade.
export function maxDepth(root) {
if (root === null) {
return 0
}
const leftDepth = maxDepth(root.left)
const rightDepth = maxDepth(root.right)
return 1 + Math.max(leftDepth, rightDepth)
}Curta, direta e alinhada com o enunciado.
O que dizer na entrevista
Uma explicação curta e boa seria:
Eu posso contar niveis com
busca em largura (BFS), mas a versão mais direta e recursiva. A profundidade de um no e 1 mais a maior profundidade entre esquerda e direita. O caso base enull -> 0.
Isso mostra que você:
- ligou o enunciado a uma definição recursiva simples
- separou bem caso base e combinação
- sabe explicar árvore sem se perder em visualizacao
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- calcular altura ou tamanho em árvore
- resolver para filhos e combinar no pai
- pensar em
busca em profundidade (DFS)recursiva - abrir caminho para balanced tree, diameter e várias outras questoes
O ponto não e decorar esse problema.
O ponto e enxergar que muita pergunta de árvore vira “resolve os filhos e combina”.