Lowest Common Ancestor of a BST

Q: Qual é a complexidade de tempo do ancestral comum mais baixo em uma BST?

O percurso a partir da raiz segue um único caminho, então leva tempo O(h) para uma árvore de profundidade h e usa espaço extra O(1) . Em uma árvore balanceada, isso é O(log n) ; em uma árvore com formato de caminho único, é O(n) .

Q: Como o LCA em uma árvore de busca binária é diferente do LCA em uma árvore binária?

Em uma árvore binária comum, um valor pode estar em qualquer lugar, então você pesquisa as duas subárvores de cada nó e o trabalho é O(n) . Em uma árvore de busca, comparar os dois valores com um nó indica em que lado cada um deles está, então você segue um caminho a partir da raiz. O método recursivo para qualquer árvore ainda funciona em uma árvore de busca, mas descarta essa informação.

Q: Um nó pode ser seu próprio ancestral comum mais baixo?

Sim. Um nó conta como ancestral de si mesmo, então, quando p está acima de q , a resposta é p . A mesma regra retorna p quando os dois valores são iguais. A busca trata dos dois casos: ela para assim que o nó atual é igual a um dos valores.

Q: Por que o percurso para no primeiro nó em que p e q se separam?

Naquele nó, um valor é menor e o outro é maior, então eles estão em subárvores diferentes. Qualquer nó abaixo dele está em apenas uma dessas subárvores e não pode conter ambos. O nó de divisão contém os dois, e nenhum nó mais profundo faz isso, o que corresponde exatamente à definição do menor ancestral comum.

MédioÁrvore binária de busca

+10

Você recebe uma árvore binária de busca armazenada no array tree em ordem por nível, e dois valores p e q que aparecem nela. A raiz fica no índice 0, os filhos do nó no índice i ficam nos índices 2*i+1 (esquerda) e 2*i+2 (direita), -1 marca uma posição vazia, e o array pode terminar com entradas -1 extras. Em uma árvore binária de busca, todo valor na subárvore esquerda de um nó é menor que o valor do nó, e todo valor na subárvore direita é maior.

Escreva uma função chamada lowestCommonAncestor que retorna o valor do ancestral comum mais baixo de p e q: o nó mais profundo que tem ambos em sua subárvore. Um nó conta como parte da própria subárvore, então, se p estiver acima de q, a resposta será o próprio p.

Função

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: a árvore binária de busca em ordem por níveis, com -1 para uma posição vazia
pinteger: o primeiro valor a encontrar
qinteger: o segundo valor a encontrar
Retornainteger: o valor do nó mais profundo que tem tanto p quanto q em sua subárvore

Restrições

1 ≤ tree.length ≤ 32767
Cada tree[i] é -1 ou um valor com 0 ≤ tree[i] ≤ 10⁵.
tree[0] nunca é -1, então a árvore tem pelo menos um nó.
A matriz pode terminar com entradas extras -1 após o último nó.
Ambos os filhos de um espaço vazio também estão vazios, e a profundidade é no máximo 14.
A árvore é uma árvore binária de busca válida, portanto todos os seus valores são distintos.
p e q são valores de nós na árvore. Eles podem vir em qualquer ordem e podem ser iguais.

Exemplos

Entrada: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Saída: 8
Explicação: O 3 é o filho à esquerda de 8, e o 15 fica abaixo de 12, à direita de 8. Subindo a partir de cada um deles, o primeiro nó que ambos alcançam é 8, então essa é a resposta; a raiz 20 também é um ancestral comum, mas está em um nível mais alto.

Entrada: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Saída: 12
Explicação: 10 é o filho esquerdo de 12. Um nó conta como seu próprio ancestral, então 12 tem os dois valores em sua subárvore, e nada abaixo dele tem: a resposta é 12. Os valores podem vir em qualquer ordem; aqui, p é o maior.

Entrada: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Saída: 70
Explicação: Tanto 55 quanto 80 são maiores que a raiz 50, então ambos ficam à direita dela. Em 70, eles seguem caminhos diferentes: 55 é menor e fica à esquerda (abaixo de 60), e 80 é maior e fica à direita. Portanto, 70 é a resposta.

+12 testes ocultos ao enviar

Para ir além

O que você mudaria se p ou q pudesse estar ausente da árvore e a função tivesse que retornar -1 nesse caso?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Em uma árvore binária comum, você não consegue saber onde um valor está sem pesquisar os dois lados de cada nó. Uma árvore de busca informa, em cada nó: os valores menores estão à esquerda, e os maiores, à direita. Então, comece pela raiz e siga em direção ao lado que contém os dois valores. O primeiro nó em que eles deixam de estar do mesmo lado é a resposta, e você o encontra seguindo um único caminho, sem nunca olhar para o restante da árvore.

Pesquise em toda a árvore, ignorando a ordem

Intuição

Primeiro, como percorrer o array. O nó no índice i tem o filho esquerdo no índice 2*i+1 e o filho direito no índice 2*i+2. Um filho só existe se seu índice estiver dentro do array e o valor nessa posição não for -1. Em [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15], a raiz 20 tem 8 e 31 nos índices 1 e 2, e o 12 no índice 4 tem 10 e 15 nos índices 9 e 10.

Este primeiro método funciona em qualquer árvore binária. Uma chamada recursiva a find(i) informa o que a subárvore no índice i contém. Uma posição vazia informa -1. Um nó que contém p ou q informa a si mesmo: ou o outro valor está abaixo dele, e então ele é a resposta, ou o outro valor está em outro lugar, e um nó mais acima encontrará ambos. Caso contrário, o nó consulta os dois filhos. Se os dois lados informarem algo, p está de um lado e q do outro, então este nó é onde eles se encontram. Se apenas um lado informar algo, passe esse resultado para cima.

Para p = 3 e q = 15, o 8 recebe o índice 3 do filho esquerdo e o índice 10 do filho direito, então informa a si mesmo. A raiz recebe esse resultado do filho esquerdo e -1 do filho direito, e passa o 8 para cima.

Está correto, mas pode visitar todos os nós: tempo O(n), com O(h) para a recursão. Ele nunca usa a ordem dos valores, que é justamente o propósito de uma árvore de busca.

Algoritmo

Escreva find(i). Se a posição em i estiver vazia (além do fim ou -1), retorne -1.
Se tree[i] for p ou q, retorne i.
Chame find em 2*i+1 e 2*i+2. Se ambos encontrarem algo, retorne i.
Caso contrário, retorne o lado que encontrou algo ou -1.
Retorne tree[find(0)].

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    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 tree[i] == -1:
            return -1
        if tree[i] == p or tree[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 tree[find(0)]

Compare os dois caminhos de busca

Intuição

Agora use a ordem. Você pode encontrar um valor da maneira como uma árvore de busca deve ser percorrida: comece na raiz, vá para a esquerda quando o valor for menor que o nó, para a direita quando for maior e pare quando encontrá-lo. Esse percurso passa por todos os ancestrais do valor e por nenhum outro nó, porque o caminho da raiz até um nó é único.

Registre o percurso de p e o percurso de q. Ambos começam na raiz e seguem pelos mesmos nós até que os valores sigam caminhos diferentes. O início compartilhado é a lista dos ancestrais comuns, então o último valor compartilhado é o mais baixo. Para 3 e 15, os caminhos são 20, 8, 3 e 20, 8, 12, 15: eles compartilham 20, 8, e a resposta é 8. Para 12 e 10, os caminhos são 20, 8, 12 e 20, 8, 12, 10, e a resposta é 12.

Cada percurso leva um passo por nível, então o tempo é O(h), no máximo 14 passos aqui, independentemente de quantos nós a árvore contém. As duas listas ocupam espaço O(h).

Algoritmo

Escreva path(target): comece no índice 0, registre tree[i], pare quando ele for igual a target; caso contrário, vá para 2*i+1 se target for menor e para 2*i+2 se for maior.
Construa o caminho até p e o caminho até q.
Percorra as duas listas desde o início enquanto os valores coincidirem, lembrando o último valor coincidente.
Retorne esse último valor compartilhado.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Desça até que os valores se separem

Intuição

Os dois caminhos coincidem enquanto p e q avançam na mesma direção, então você não precisa armazená-los. Percorra ambos ao mesmo tempo. Em um nó que contém v, se os dois valores forem menores que v, ambos estão na subárvore esquerda, assim como todo ancestral comum abaixo de v: vá para a esquerda. Se ambos forem maiores, vá para a direita.

Caso contrário, você chegou ao destino. Ou um valor é menor que v e o outro é maior, então eles estão em subárvores diferentes e nenhum filho de v contém ambos; ou um deles é igual a v, e um nó é ancestral de si mesmo. De qualquer forma, v é o nó mais profundo acima de ambos.

No terceiro exemplo, a raiz 50 está abaixo de 55 e 80, então você vai para a direita, em direção a 70. Ali, 55 é menor e 80 é maior: a resposta é 70. No segundo exemplo, você vai de 20 para 8 e depois para 12, que é igual a p, e para.

Você segue um único caminho a partir da raiz, com um par de comparações por nível, então o tempo é O(h) e o espaço é O(1). O restante da árvore nunca é lido.

Algoritmo

Comece no índice i = 0.
Leia v = tree[i].
Se p < v e q < v, vá para 2*i+1 e repita.
Se p > v e q > v, vá para 2*i+2 e repita.
Caso contrário, retorne v.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

Armadilhas e casos extremos

O percurso é curto, então a maioria dos bugs vem da regra de parada.

Usar ≤ e ≥ nos testes de movimento. Com p = 12 e q = 10, o teste p ≤ 12 e q ≤ 12 passa da resposta para 10 e, a partir daí, o percurso retorna 10 ou sai da árvore. Avance somente quando os dois valores estiverem estritamente do mesmo lado.
Pressupor que p < q. Os valores podem vir em qualquer ordem. Teste ambos em relação ao nó ou troque-os primeiro para que p seja o menor.
Esquecer que um dos valores pode ser ancestral do outro. Nesse caso, a resposta é o próprio valor, não o pai dele.
Retornar o índice em vez do valor. A função retorna tree[i], não i.
Pesquisar a árvore inteira. Isso dá a resposta certa, mas visita todos os nós, quando basta seguir um caminho.
Confundir o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para a aritmética 2*i+1 e leia tree[i + 1].

Perguntas frequentes4

Qual é a complexidade de tempo do ancestral comum mais baixo em uma BST?

O percurso a partir da raiz segue um único caminho, então leva tempo O(h) para uma árvore de profundidade h e usa espaço extra O(1). Em uma árvore balanceada, isso é O(log n); em uma árvore com formato de caminho único, é O(n).

Como o LCA em uma árvore de busca binária é diferente do LCA em uma árvore binária?

Em uma árvore binária comum, um valor pode estar em qualquer lugar, então você pesquisa as duas subárvores de cada nó e o trabalho é O(n). Em uma árvore de busca, comparar os dois valores com um nó indica em que lado cada um deles está, então você segue um caminho a partir da raiz. O método recursivo para qualquer árvore ainda funciona em uma árvore de busca, mas descarta essa informação.

Um nó pode ser seu próprio ancestral comum mais baixo?

Sim. Um nó conta como ancestral de si mesmo, então, quando p está acima de q, a resposta é p. A mesma regra retorna p quando os dois valores são iguais. A busca trata dos dois casos: ela para assim que o nó atual é igual a um dos valores.

Por que o percurso para no primeiro nó em que p e q se separam?

Naquele nó, um valor é menor e o outro é maior, então eles estão em subárvores diferentes. Qualquer nó abaixo dele está em apenas uma dessas subárvores e não pode conter ambos. O nó de divisão contém os dois, e nenhum nó mais profundo faz isso, o que corresponde exatamente à definição do menor ancestral comum.

Python

def lowestCommonAncestor(tree, p, q):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Esperado

Lowest Common Ancestor of a BST

Função

Restrições

Exemplos

Dicas

Solução

Pesquise em toda a árvore, ignorando a ordem

Compare os dois caminhos de busca

Desça até que os valores se separem

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos