24 de Março
K-ésimo menor elemento em uma árvore binária de busca
Como usar o percurso em ordem para explorar a ordem natural da árvore binaria de busca e parar assim que o contador chega em k.
Árvores Intermediario 15 min TypeScript
Dada a raiz de uma árvore binaria de busca e um inteiro k, retorne o k-esimo menor valor da árvore.
Considere k como indice baseado em 1.
Exemplo:
Input:
root = [3,1,4,null,2]
k = 1
Output:
1
O que perceber antes de codar
- Em árvore binaria de busca, o percurso em ordem já sai ordenado. Não precisa ordenar depois.
- `k` e baseado em 1, entao o primeiro visitado nesse percurso já pode ser a resposta.
- Se você só precisa do k-esimo, pode parar cedo.
Erros comuns
- tratar `k` como se fosse baseado em 0
- ignorar a propriedade da árvore binaria de busca e percorrer como se fosse uma árvore qualquer
Passo 1 - Lembrar o que a árvore te entrega de graca
Em uma árvore binaria de busca:
- tudo da esquerda e menor
- tudo da direita e maior
Isso significa que existe uma travessia que já devolve os valores em ordem.
Essa travessia e o percurso em ordem:
- esquerda
- no atual
- direita
Passo 2 - Escrever a versão inicial mais direta
A versão inicial boa e:
- fazer o percurso em ordem completo
- guardar os valores em array
- devolver
values[k - 1]
Funciona e deixa a propriedade ordenada bem visível.
Passo 3 - Perguntar o que realmente precisa ser guardado
O problema não pede todos os valores ordenados.
Ele pede só:
- o k-esimo visitado
Entao talvez um array inteiro seja mais do que você precisa.
Passo 4 - Contar durante o percurso em ordem e parar cedo
Em vez de guardar tudo, você pode:
- manter um contador
- incrementar a cada visita real
- parar quando o contador chegar em
k
Isso transforma a propriedade da árvore em resposta direta.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function kthSmallest(root, k) {
// root is an object like { val: number, left: ..., right: ... } or null
// sua solução aqui
return null
}
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(h + k)
Espaço: O(h)
Solução 1 - Percurso em ordem completo mais array
Boa versão inicial porque deixa a ordem natural da árvore bem explicita.
export function kthSmallest(root, k) {
const values = []
function inorder(node) {
if (node === null) {
return
}
inorder(node.left)
values.push(node.val)
inorder(node.right)
}
inorder(root)
return values[k - 1] ?? null
}Funciona.
Mas guarda mais estado do que o problema realmente pede.
Solução 2 - Percurso em ordem com contador e parada antecipada na busca em profundidade (DFS)
Agora a travessia para assim que encontra a resposta.
export function kthSmallest(root, k) {
let seen = 0
let result = null
function inorder(node) {
if (node === null || result !== null) {
return
}
inorder(node.left)
if (result !== null) {
return
}
seen += 1
if (seen === k) {
result = node.val
return
}
inorder(node.right)
}
inorder(root)
return result
}O insight forte aqui e que esse percurso não e só uma travessia bonita. E a forma de ler a árvore binaria de busca em ordem.
O que dizer na entrevista
Uma explicação curta e boa seria:
Como a estrutura e uma árvore binaria de busca, o percurso em ordem visita os valores em ordem crescente. A versão inicial faz esse percurso completo e pega
values[k - 1]. A versão melhor só conta quantos nos já visitou e para assim que chega nok-esimo, sem precisar guardar tudo, entao a travessia só vai até onde a resposta obrigar.
Isso mostra que você:
- usou uma propriedade da estrutura, não força bruta
- deixou claro por que o percurso em ordem e a travessia certa
- evitou estado desnecessario
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- ler árvore binaria de busca em ordem crescente
- buscar posição relativa em estrutura ordenada
- transformar travessia em contador
- decidir quando vale parar cedo numa
busca em profundidade (DFS)
O ponto não e decorar esse problema.
O ponto e aprender quando a ordem já esta embutida na própria estrutura.