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ê pode pesquisar todos os nós, com trabalho O(n). Em uma árvore de busca, comparar os dois valores com um nó informa em que lado cada um está, então você segue um caminho a partir da raiz.

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

Sim. Um nó é considerado ancestral de si mesmo, então, quando p está acima de q , a resposta é p , e, quando os dois valores são iguais, a resposta é esse valor.

MédioÁrvore binária de busca

+10

Você recebe uma árvore de busca binária armazenada no formato heap no array tree: a raiz está no índice 0, os filhos do índice i estão em 2*i+1 (esquerda) e 2*i+2 (direita), e -1 marca uma posição vazia. Todo valor em um nó da subárvore esquerda é menor que o valor do nó, e todo valor em sua subárvore direita é maior.

Escreva lowestCommonAncestor, que retorna o valor do ancestral comum mais baixo dos valores p e q, ambos na árvore: o nó mais profundo que tem ambos em sua subárvore. Um nó faz parte da própria subárvore, então, se p estiver acima de q, a resposta será p.

Função

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

treeinteger-array: a árvore de busca binária em ordem por nível, com -1 para um espaço vazio
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ó.
O array pode terminar com entradas -1 extras após o último nó.
Ambos os filhos de uma posição vazia 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 estar em qualquer ordem e ser iguais.

Exemplos

Entrada: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Saída: 8
Explicação: Subindo a partir de 3 e de 15, o primeiro nó que ambos alcançam é 8: 3 é seu filho à esquerda e 15 está abaixo de 12, à sua direita. A raiz 20 também é um ancestral comum, mas está mais acima.

Entrada: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Saída: 12
Explicação: 10 é o filho à esquerda de 12, e um nó é considerado seu próprio ancestral, então 12 contém ambos os valores e nenhum nó abaixo dele os contém. Aqui, p é o maior valor.

Entrada: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Saída: 70
Explicação: Ambos os valores são maiores que a raiz 50, então ambos ficam à direita dela. Em 70, eles se separam: 55 é menor e fica à esquerda, abaixo de 60, e 80 é maior.

Para ir além

O que você mudaria se p ou q pudesse estar faltando na á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

Uma árvore de busca indica, em cada nó, onde um valor está: os menores ficam à esquerda, os maiores, à direita. Comece pela raiz e siga em direção ao lado que contém os dois valores. O primeiro nó em que eles deixam de compartilhar o mesmo lado é a resposta, e você chega até ele por um único caminho.

Pesquise em toda a árvore, ignorando a ordem

Intuição

Este método funciona em qualquer árvore binária. Uma chamada recursiva a find(i) informa o que a subárvore em i contém. Um nó que contém p ou q retorna a si mesmo: se o outro valor estiver abaixo dele, ele é a resposta; caso contrário, um nó mais acima encontra ambos. Qualquer outro nó consulta os dois filhos. Se ambos retornarem algo, p e q estão em lados diferentes, e este nó é onde eles se encontram; se apenas um retornar algo, repasse esse resultado para cima.

Para 3 e 15, o 8 recebe o índice 3 da esquerda e o índice 10 da direita e retorna a si mesmo. Ele pode visitar todos os nós: tempo O(n) e O(h) para a recursão.

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

Procure um valor da maneira usual: a partir da raiz, vá para a esquerda quando ele for menor que o nó e para a direita quando for maior. O caminho da raiz até um nó é único, então o percurso passa por todos os ancestrais do valor e por nenhum outro nó.

Registre os dois percursos. Eles compartilham nós até os valores seguirem caminhos diferentes, então o início compartilhado lista os ancestrais comuns, e seu último valor é o mais baixo. Para 3 e 15, os caminhos são 20, 8, 3 e 20, 8, 12, 15: eles compartilham 20, 8, então a resposta é 8. Cada percurso leva uma etapa por nível: tempo O(h) e espaço O(h) para as listas.

Algoritmo

Escreva path(target): comece no índice 0, registre tree[i], pare quando ele for igual a target; caso contrário, avance 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 e retorne o último valor que elas têm em comum.

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 dividam

Intuição

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

Caso contrário, um valor é menor e o outro, maior, então nenhum filho de v contém ambos, ou um deles é igual a v, que é seu próprio ancestral. De qualquer forma, v é o nó mais profundo acima de ambos. No terceiro exemplo, 50 está abaixo dos dois valores, então você segue para a direita até 70, onde 55 é menor e 80 é maior. Um par de comparações por nível resulta em tempo O(h) e espaço O(1).

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

Usar ≤ e ≥ nos testes de movimento. Com p = 12 e q = 10, a busca passa por 12 até chegar a 10 e então retorna 10 ou sai da árvore.
Supor que p < q. No segundo exemplo, p é o valor maior. Teste ambos em relação ao nó ou troque-os antes.
Retornar o índice em vez do valor. A resposta é tree[i], não i.
Em Lua e R, os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para a operação aritmética 2*i+1 e leia tree[i + 1].

Perguntas frequentes3

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ê pode pesquisar todos os nós, com trabalho O(n). Em uma árvore de busca, comparar os dois valores com um nó informa em que lado cada um está, então você segue um caminho a partir da raiz.

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

Sim. Um nó é considerado ancestral de si mesmo, então, quando p está acima de q, a resposta é p, e, quando os dois valores são iguais, a resposta é esse valor.

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

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

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 dividam

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos