24 de Março
Inverter árvore binária
Como perceber que inverter uma árvore e só trocar esquerda e direita em cada no e deixar a recursão cuidar do resto.
Árvores Iniciante 10 min TypeScript
Dada a raiz de uma árvore binaria, inverta a árvore e retorne a raiz.
Inverter significa espelhar esquerda e direita em todos os nos.
Exemplo:
Input: [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
O que perceber antes de codar
- O problema muda a estrutura da árvore, não os valores.
- Árvore vazia continua valida.
- A mesma regra vale para todos os nos.
Erros comuns
- trocar os filhos de um no e esquecer de continuar a recursão
- sobrescrever um lado antes de guardar o outro
Passo 1 - Parar de pensar na árvore inteira de uma vez
Muita gente trava em problema de árvore porque tenta visualizar tudo ao mesmo tempo.
Aqui não precisa.
A pergunta certa e menor:
- o que precisa acontecer neste no?
Passo 2 - Descobrir a regra local
Em cada no, inverter significa:
- o que era
leftviraright - o que era
rightviraleft
Só isso.
Passo 3 - Escrever uma versão inicial que deixa a ideia visível
Uma versão inicial valida e construir uma árvore nova espelhada com recursao:
- copia o valor
- monta a esquerda a partir da direita antiga
- monta a direita a partir da esquerda antiga
Funciona e deixa a recursão explicita.
Passo 4 - Perceber que nem precisa criar árvore nova
Se você pode modificar o no atual, basta:
- inverter os filhos
- devolver o próprio no
A recursao cuida do resto.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function invertTree(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// sua solução aqui
return root
}
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 - Construir uma árvore nova espelhada
Boa versão inicial porque mostra a regra sem efeito colateral.
export function invertTree(root) {
if (root === null) {
return null
}
return {
val: root.val,
left: invertTree(root.right),
right: invertTree(root.left),
}
}Funciona, mas cria estrutura nova sem necessidade.
Solução 2 - Trocar em-place com recursao e DFS implicita
Agora você reaproveita a própria árvore.
export function invertTree(root) {
if (root === null) {
return null
}
const left = invertTree(root.left)
const right = invertTree(root.right)
root.left = right
root.right = left
return root
}O ponto principal e que a recursão devolve os filhos já invertidos. A partir disso, você só reconecta.
O que dizer na entrevista
Uma explicação curta e boa seria:
Eu penso localmente. Para cada no, preciso trocar esquerda e direita. A
recursaoresolve os filhos, e depois eu reconecto os dois lados no no atual. Isso visita cada no uma vez emO(n).
Isso mostra que você:
- não se perde tentando visualizar a árvore inteira
- sabe transformar regra local em recursão
- entende o que a função devolve em cada chamada
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- aplicar a mesma regra em todos os nos
- resolver subarvores e combinar no pai
- pensar em árvore via recursão local
- preparar terreno para depth, traversal, BST e LCA
O ponto não e decorar
invertTree.
O ponto e aprender a perguntar “o que acontece neste no?”.