Lowest Common Ancestor of a Binary Tree
Você recebe uma árvore binária no array root, na ordem de heap: a raiz no índice 0, os filhos do índice i em 2*i+1 (esquerdo) e 2*i+2 (direito), e -1 para uma posição vazia. Os valores são distintos e não seguem nenhuma ordem.
Retorne o valor do ancestral comum mais baixo de p e q, os valores de dois nós diferentes: o nó mais profundo cuja subárvore contém ambos. Uma subárvore inclui seu nó superior, então, se q estiver abaixo de p, a resposta é p.
Função
- rootinteger-array
- a árvore binária em ordem por nível, com -1 para uma posição vazia
- pinteger
- o valor de um nó
- qinteger
- o valor de outro nó
- Retornainteger
- o valor do nó mais baixo cuja subárvore contém tanto p quanto q
Restrições
2 ≤ root.length ≤ 32767- Cada
root[i]é-1ou um valor com0 ≤ root[i] ≤ 104. root[0]nunca é-1, e a árvore tem pelo menos dois nós.- O array pode terminar com entradas
-1extras após o último nó. - Os dois filhos de um espaço vazio também estão vazios, e a profundidade é no máximo
14. - Todos os valores na árvore são distintos e não seguem nenhuma ordem.
peqsão os valores de dois nós diferentes na árvore, em qualquer ordem.
Exemplos
- Entrada
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
- Saída
- 3
- Explicação
6é o filho à esquerda de3, e9fica abaixo de4, à direita de3, então eles se encontram em3. Comparar os valores apontaria para a raiz8:6é menor e9é maior.
- Entrada
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
- Saída
- 4
- Explicação
7é o filho à esquerda de4, e a subárvore de4inclui o próprio4, então a resposta é4.
- Entrada
- root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
- Saída
- 6
- Explicação
- A raiz
1não tem filho à esquerda. Seu filho à direita6tem3à esquerda e0à direita, então os valores se encontram em6.
Para ir além
Se p ou q puderem estar ausentes, sendo -1 a resposta, qual atalho na passagem única falha e como você ainda termina em uma única travessia?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Experimente a regra da árvore de busca no primeiro exemplo:
6é menor que a raiz8e9é maior. Onde eles realmente ficam? O que isso diz sobre a comparação de valores nesta árvore?Deixe cada subárvore informar ao seu pai o que encontrou: nada, um dos dois valores ou a resposta. Um nó que recebe informações sobre um valor de ambos os filhos é onde
peqse encontram.Escreva uma função recursiva
find(i)que retorne-1para uma posição vazia,iquandoroot[i]forpouq,iquando ambos os filhos retornarem um índice e, caso contrário, o resultado do filho que não seja-1. A resposta éroot[find(0)].
Solução
Nenhuma ordem indica a você qual lado contém um valor, então você precisa verificar. Uma passagem em pós-ordem permite que cada subárvore informe o que encontrou, e os valores se encontram no primeiro nó que recebe informações dos dois lados.
Desça, procurando em cada lado
Intuição
Desça a partir da raiz e, em cada nó, procure p e q na subárvore esquerda. Se ambos estiverem lá: vá para a esquerda. Se nenhum estiver: vá para a direita. Se houver um em cada lado: os valores se separam, e esse nó é a resposta. Um nó que contém p ou q também é a resposta, pois o outro valor necessariamente estará abaixo dele. Para 6 e 9, a raiz encontra ambos à sua esquerda, e em 3 o único 6 contém apenas p.
Cada passo para baixo pesquisa uma subárvore inteira, então h níveis custam O(n·h), e O(n²) em uma árvore alta e estreita, sem limite de profundidade. A pesquisa em 8 já visitou todos os nós abaixo de 3, e o passo em 3 visita alguns deles novamente.
Algoritmo
- Escreva
contains(i, value):falsepara uma posição vazia (após o fim ou-1),trueseroot[i]for igual avalue; caso contrário, consulte ambos os filhos. - Comece em
i = 0. Seroot[i]forpouq, retorne-o. - Se a subárvore à esquerda, em
2*i+1, contiver ambos os valores, vá para lá. Se não contiver nenhum deles, vá para2*i+2. - Caso contrário, retorne
root[i].
def lowestCommonAncestor(root, p, q):
n = len(root)
def contains(i, value):
# Is value somewhere in the subtree at index i?
if i >= n or root[i] == -1:
return False
if root[i] == value:
return True
return contains(2 * i + 1, value) or contains(2 * i + 2, value)
i = 0 # p and q are always inside the subtree at i
while True:
if root[i] == p or root[i] == q:
return root[i] # one value is here, the other is below it
left = 2 * i + 1
p_left = contains(left, p)
q_left = contains(left, q)
if p_left and q_left:
i = left # both on the left
elif not p_left and not q_left:
i = 2 * i + 2 # both on the right
else:
return root[i] # one on each sideUma passagem em pós-ordem
Intuição
Faça cada subárvore responder uma vez, de baixo para cima. find(i) retorna o índice da resposta se a subárvore em i contiver ambos os valores, o índice de p ou q se contiver um deles, e -1 se não contiver nenhum.
Um nó que contém p ou q retorna seu próprio índice sem verificar abaixo. Se o outro valor estiver em sua subárvore, este nó é a resposta; caso contrário, um nó acima recebe informações dos dois lados. Qualquer outro nó consulta ambos os filhos. Dois resultados significam que os valores vieram de lados diferentes e se encontram aqui. Um único resultado sobe sem alterações, seja um dos valores ou a resposta final.
No primeiro exemplo, 3 recebe o índice 3 da esquerda e 10 da direita, retorna seu próprio índice 1, e a raiz o repassa. Cada nó é visitado uma vez: tempo O(n), recursão O(h).
Algoritmo
find(i)retorna-1para um índice além do fim ou um-1.- Um nó cujo valor é
pouqretornaisem procurar abaixo. - Qualquer outro nó calcula
left = find(2*i+1)eright = find(2*i+2). Se nenhum dos dois for-1, retornai; caso contrário, retorna aquele que não é-1, ou-1. - Retorne
root[find(0)].
def lowestCommonAncestor(root, p, q):
n = len(root)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or root[i] == -1:
return -1
if root[i] == p or root[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return root[find(0)]
Armadilhas e casos extremos
- Comparar valores com o nó. A árvore não tem ordenação: no primeiro exemplo, essa busca para na raiz
8em vez de3. - Passar
trueoufalseem vez de um índice. O nó pai não consegue saber se a resposta final já está abaixo dele. - Ler um nó filho sem verificar o comprimento. O
9no índice10tem índices de filhos21e22, além da última entrada. - Retornar
find(0), um índice, em vez deroot[find(0)]. - Em Lua e R, os arrays começam em 1: mantenha os índices dos nós começando em 0 e leia
root[i + 1].
Perguntas frequentes3
Qual é a complexidade de tempo do ancestral comum mais baixo de uma árvore binária?
A passagem em pós-ordem visita cada nó no máximo uma vez: tempo O(n). A pilha de recursão mantém um quadro por nível, portanto o espaço é O(log n) em uma árvore balanceada e O(n) em uma árvore com formato de caminho.
Em que isso difere do ancestral comum mais baixo em uma árvore de busca binária?
Em uma árvore de busca, comparar p e q com um nó informa em que lado cada um está, então um caminho a partir da raiz encontra a resposta em O(h). Aqui, uma comparação não informa nada, então você busca nas subárvores.
Você consegue encontrar o ancestral comum mais baixo usando ponteiros para os pais?
Sim. Neste array, o pai do índice i é (i-1)/2 arredondado para baixo. Mova o maior dos dois índices para o pai dele até que sejam iguais; um índice maior nunca é ancestral de um menor. Com nós encadeados, coloque os ancestrais de p em um conjunto e suba a partir de q até o primeiro que estiver nele.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def lowestCommonAncestor(root, p, q):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9] p = 6 q = 9
Saída Esperada
3