24 de Março
Subárvore de outra árvore
Como procurar uma subarvore de verdade comparando forma e valores, não só nos que parecem bater.
Árvores Intermediario 18 min TypeScript
Dadas duas árvores binarias root e subRoot, retorne true se existir um no em root cuja subarvore seja exatamente igual a subRoot.
Igual aqui significa:
- mesmos valores
- mesma estrutura
Exemplo:
Input:
root = [3,4,5,1,2]
subRoot = [4,1,2]
Output:
true
O que perceber antes de codar
- Um valor igual na raiz não garante que a subarvore inteira bate.
- O problema pede igualdade estrutural, não só "contem estes valores".
- Em cada no da árvore maior, você decide se vale testar igualdade completa ou continuar procurando.
Erros comuns
- comparar só o valor da raiz e ignorar filhos
- esquecer que `subRoot = null` deve ser considerada subarvore valida
Passo 1 - Entender o que "ser subarvore" realmente pede
Muita gente le isso como:
- "tem um no com o mesmo valor?"
Não e isso.
O ponto e:
- a partir de algum no de
root - a estrutura inteira precisa bater com
subRoot
Passo 2 - Escrever uma versão inicial bem direta
Uma versão inicial possível e:
- serializar
subRoot - serializar cada subarvore de
root - comparar as strings
Funciona se você colocar marcadores de null.
Mas repete serialização demais.
Passo 3 - Separar as duas perguntas
Em qualquer no de root, existem duas perguntas diferentes:
- esta árvore e exatamente igual a
subRoot? - se não for aqui, a resposta esta na esquerda ou na direita?
Quando você separa isso, a recursão fica limpa.
Passo 4 - Criar uma função auxiliar de igualdade estrutural
A função de igualdade precisa checar:
- os dois
nullao mesmo tempo - valor atual
- esquerda com esquerda
- direita com direita
Depois disso, a busca principal só tenta essa comparação em cada candidato.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function isSubtree(root, subRoot) {
// root and subRoot are objects 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 * m)
Espaço: O(h)
Solução 1 - Serializar cada candidata e comparar
Boa versão inicial porque deixa visível que o problema pede estrutura, não só valores.
function serialize(node): string {
if (node === null) {
return "#"
}
return `${node.val},${serialize(node.left)},${serialize(node.right)}`
}
export function isSubtree(root, subRoot) {
if (subRoot === null) {
return true
}
const target = serialize(subRoot)
const candidates: string[] = []
function collect(node) {
if (node === null) {
return
}
candidates.push(serialize(node))
collect(node.left)
collect(node.right)
}
collect(root)
return candidates.includes(target)
}Funciona.
Mas reserializa várias subarvores inteiras sem necessidade.
Solução 2 - Comparação estrutural com busca em DFS por recursao
Agora cada no de root só vira um candidato de verdade quando a comparação faz sentido.
function isSameTree(a, b) {
if (a === null && b === null) {
return true
}
if (a === null || b === null) {
return false
}
return (
a.val === b.val &&
isSameTree(a.left, b.left) &&
isSameTree(a.right, b.right)
)
}
export function isSubtree(root, subRoot) {
if (subRoot === null) {
return true
}
if (root === null) {
return false
}
if (isSameTree(root, subRoot)) {
return true
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}O insight forte aqui e que a busca e sobre candidatos, mas a confirmação e sempre estrutural.
O que dizer na entrevista
Uma explicação curta e boa seria:
Eu separo o problema em duas funções.
isSameTreeresponde se duas árvores sao exatamente iguais em valor e estrutura.isSubtreepercorre a árvore maior procurando um ponto onde essa comparação completa passe. Isso evita tratar um valor igual como se ele já provasse a subarvore.
Isso mostra que você:
- entendeu a diferença entre valor local e igualdade estrutural
- decompos o problema em duas responsabilidades claras
- explicou a recursão sem virar teatro
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- comparar estruturas recursivas
- distinguir candidato local de confirmação global
- usar função auxiliar para igualdade de árvore ou lista
- reconhecer quando “parece igual” ainda não prova nada
O ponto não e decorar
isSubtree.
O ponto e aprender a separar busca de confirmação estrutural.