24 de Março
Validar árvore binária de busca
Como validar árvore binaria de busca propagando limites na recursão em vez de fazer comparações locais que parecem certas mas quebram.
Árvores Intermediario 20 min TypeScript
Dada a raiz de uma árvore binaria, retorne true se ela for uma árvore binaria de busca valida e false caso contrario.
Em uma árvore binaria de busca valida:
- todos os nos da subarvore esquerda sao menores que o no atual
- todos os nos da subarvore direita sao maiores que o no atual
- as duas subarvores também precisam ser árvores binarias de busca validas
Exemplo:
Input: [2,1,3]
Output: true
O que perceber antes de codar
- A regra da árvore binaria de busca e global, não só local.
- Duplicatas invalidam a árvore binaria de busca neste problema.
- Um no pode respeitar o pai e ainda assim violar um limite vindo de cima.
Erros comuns
- comparar cada no só com o pai direto
- aceitar valores iguais na esquerda ou na direita
Passo 1 - Ver onde a checagem local engana
Muita gente começa com:
- esquerda menor que o pai
- direita maior que o pai
Parece certo.
Mas não basta.
Um no pode respeitar o pai direto e ainda violar a raiz la em cima.
Passo 2 - Escrever uma versão inicial que deixa isso mais visível
Uma versão inicial valida e:
- percorrer a árvore em ordem
- guardar os valores em array
- checar se a sequência ficou estritamente crescente
Funciona porque percorrer em ordem uma árvore binaria de busca valida gera uma sequência ordenada.
Passo 3 - Perguntar qual restrição cada no realmente carrega
Cada no não herda só o pai.
Ele herda um intervalo inteiro de valores validos.
Exemplo:
- se você entrou na subarvore direita da raiz
5, tudo dali precisa ser maior que5 - isso continua valendo vários niveis abaixo
Passo 4 - Propagar limites na recursao
Entao a função pode carregar:
minmax
E cada no precisa respeitar:
min < node.val < max
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function isValidBST(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// sua solução aqui
return false
}
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 - Inorder e checagem de ordem
Boa versão inicial porque revela a propriedade da árvore sem cair no erro do pai direto.
export function isValidBST(root) {
const values = []
function inorder(node) {
if (node === null) {
return
}
inorder(node.left)
values.push(node.val)
inorder(node.right)
}
inorder(root)
for (let index = 1; index < values.length; index += 1) {
if (values[index] <= values[index - 1]) {
return false
}
}
return true
}Funciona bem, mas guarda uma estrutura que não precisa.
Solução 2 - Busca em profundidade (DFS) com limites
Agora a regra global vira parte da recursão.
export function isValidBST(root) {
function validate(node, min, max) {
if (node === null) {
return true
}
if (node.val <= min || node.val >= max) {
return false
}
return validate(node.left, min, node.val) && validate(node.right, node.val, max)
}
return validate(root, -Infinity, Infinity)
}Essa versão captura o coracao do problema: cada chamada herda um intervalo valido.
O que dizer na entrevista
Uma explicação curta e boa seria:
O erro comum e comparar cada no só com o pai. A regra correta da árvore binaria de busca e global. Entao eu propago um intervalo valido na
recursao. Cada no precisa estar estritamente entreminemax, e esses limites vao ficando mais apertados conforme desco a árvore. Isso ainda visita cada no uma vez emO(n).
Isso mostra que você:
- enxergou o erro clássico da solução ruim
- modelou a restrição do jeito certo
- explicou a regra global com clareza
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- propagar restrições na
recursao - validar estrutura com regra global
- raciocinar com intervalos em árvore
- resolver problemas em que o contexto do avo ainda importa
O ponto não e decorar esse problema.
O ponto e aprender quando comparar localmente não basta.