Lowest Common Ancestor of a BST

Q: Jaka jest złożoność czasowa znajdowania najniższego wspólnego przodka w BST?

Przejście od korzenia przebiega jedną ścieżką, więc zajmuje O(h) czasu dla drzewa o głębokości h i O(1) dodatkowej pamięci. W przypadku zrównoważonego drzewa jest to O(log n); w przypadku drzewa przypominającego pojedynczą ścieżkę jest to O(n).

Q: Czym różni się LCA w binarnym drzewie wyszukiwań od LCA w drzewie binarnym?

W zwykłym drzewie binarnym wartość może znajdować się w dowolnym miejscu, więc możesz przeszukać każdy węzeł — to O(n) pracy. W drzewie wyszukiwań porównanie tych dwóch wartości z wartością w węźle wskazuje, po której stronie znajduje się każda z nich, więc podążasz jedną ścieżką od korzenia.

Q: Czy węzeł może być swoim własnym najniższym wspólnym przodkiem?

Tak. Węzeł jest swoim własnym przodkiem, więc gdy p znajduje się wyżej niż q , odpowiedzią jest p , a gdy obie wartości są równe, odpowiedzią jest ta wartość.

ŚrednieDrzewo BST

+10

Otrzymujesz drzewo binarne przeszukiwania zapisane w tablicy tree w porządku kopca: korzeń znajduje się pod indeksem 0, dzieci węzła o indeksie i znajdują się pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), a -1 oznacza puste miejsce. Każda wartość w lewym poddrzewie węzła jest mniejsza od wartości tego węzła, a każda wartość w jego prawym poddrzewie jest większa.

Napisz lowestCommonAncestor, która zwraca wartość najniższego wspólnego przodka wartości p i q, z których obie znajdują się w drzewie: najgłębiej położonego węzła, który ma obie wartości w swoim poddrzewie. Węzeł należy do własnego poddrzewa, więc jeśli p znajduje się nad q, odpowiedzią jest p.

Funkcja

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

treeinteger-array: binarne drzewo wyszukiwań w kolejności poziomami, z -1 oznaczającym puste miejsce
pinteger: pierwsza wartość do znalezienia
qinteger: drugą wartość do znalezienia
Zwracainteger: wartość najgłębszego węzła, który ma zarówno p, jak i q w swoim poddrzewie

Ograniczenia

1 ≤ tree.length ≤ 32767
Każde tree[i] ma wartość -1 lub wartość z zakresu 0 ≤ tree[i] ≤ 10⁵.
tree[0] nigdy nie jest równe -1, więc drzewo ma co najmniej jeden węzeł.
Tablica może kończyć się dodatkowymi wpisami -1 za ostatnim węzłem.
Oboje dzieci pustego miejsca również są puste, a głębokość wynosi co najwyżej 14.
Drzewo jest prawidłowym binarnym drzewem wyszukiwań, więc wszystkie jego wartości są różne.
p i q to wartości węzłów w drzewie. Mogą występować w dowolnej kolejności i mogą być równe.

Przykłady

Wejście: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Wyjście: 8
Wyjaśnienie: Wspinając się od 3 i od 15, pierwszym wspólnym węzłem, do którego docierają, jest 8: 3 jest jego lewym dzieckiem, a 15 znajduje się poniżej 12 po jego prawej stronie. Korzeń 20 również jest wspólnym przodkiem, ale znajduje się wyżej.

Wejście: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Wyjście: 12
Wyjaśnienie: 10 jest lewym dzieckiem 12, a węzeł jest uznawany za swojego własnego przodka, więc 12 zawiera obie wartości, a żaden węzeł poniżej niego ich nie zawiera. Tutaj p jest większą wartością.

Wejście: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Wyjście: 70
Wyjaśnienie: Obie wartości są większe od korzenia 50, więc obie znajdują się po jego prawej stronie. Przy 70 ich ścieżki się rozchodzą: 55 jest mniejsza i znajduje się po lewej stronie, poniżej 60, a 80 jest większa.

Pytanie dodatkowe

Co byś zmienić, gdyby w drzewie mogło brakować p lub q, a funkcja musiałaby wtedy zwrócić -1?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Drzewo wyszukiwań wskazuje przy każdym węźle, gdzie znajduje się dana wartość: mniejsze wartości są po lewej, większe po prawej. Zacznij od korzenia i przechodź w stronę, po której znajdują się obie wartości. Odpowiedzią jest pierwszy węzeł, przy którym wartości przestają znajdować się po tej samej stronie; dotrzesz do niego jedną ścieżką.

Przeszukaj całe drzewo, ignorując kolejność

Intuicja

Ta metoda działa na każdym drzewie binarnym. Rekurencyjna funkcja find(i) informuje, co zawiera poddrzewo w i. Węzeł zawierający p lub q zwraca sam siebie: jeśli druga wartość znajduje się niżej, jest odpowiedzią, a jeśli nie, węzeł położony wyżej zobaczy obie wartości. Każdy inny węzeł pyta oboje swoich dzieci. Jeśli oba coś zwrócą, p i q znajdują się po różnych stronach, a ten węzeł jest miejscem, w którym się spotykają; jeśli coś zwróci tylko jedno, przekaż to wyżej.

Dla 3 i 15 węzeł 8 otrzymuje indeks 3 z lewej strony i indeks 10 z prawej, po czym zwraca sam siebie. Może odwiedzić każdy węzeł: czas O(n) i O(h) dla rekurencji.

Algorytm

Napisz find(i). Jeśli miejsce pod indeksem i jest puste (indeks jest poza końcem lub ma wartość -1), zwróć -1.
Jeśli tree[i] ma wartość p lub q, zwróć i.
Wywołaj find dla 2*i+1 i 2*i+2. Jeśli w obu przypadkach coś znaleziono, zwróć i.
W przeciwnym razie zwróć wynik z tej strony, po której coś znaleziono, albo -1.
Zwróć 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)]

Porównaj dwie ścieżki wyszukiwania

Intuicja

Szukaj wartości w zwykły sposób: zacznij od korzenia, idź w lewo, gdy jest mniejsza od wartości w węźle, a w prawo, gdy jest większa. Ścieżka od korzenia do węzła jest unikalna, więc podczas przechodzenia trafisz na każdego przodka szukanej wartości i na nic więcej.

Zapisz obie ścieżki. Mają wspólne węzły, dopóki ścieżki nie rozchodzą się w różne strony, więc ich wspólny początek zawiera listę wspólnych przodków, a ostatnia wartość z tej listy jest najniższa. Dla 3 i 15 ścieżki to 20, 8, 3 oraz 20, 8, 12, 15: mają wspólne 20, 8, więc odpowiedzią jest 8. Każde przejście wymaga jednego kroku na poziom: czas O(h) i pamięć O(h) na listy.

Algorytm

Napisz path(target): zacznij od indeksu 0, zapisz tree[i], zatrzymaj się, gdy będzie równy target, w przeciwnym razie przejdź do 2*i+1, jeśli target jest mniejszy, a do 2*i+2, jeśli jest większy.
Zbuduj ścieżkę do p i ścieżkę do q.
Przejdź obie listy od początku i zwróć ostatnią wspólną im wartość.

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

Schodź w dół, aż wartości się rozdzielą

Intuicja

Obie ścieżki są zgodne, gdy p i q podążają w tę samą stronę, więc przechodź obiema naraz. W węźle zawierającym v, jeśli obie wartości są mniejsze, obie znajdują się w lewym poddrzewie, podobnie jak każdy wspólny przodek poniżej v: idź w lewo. Jeśli obie są większe, idź w prawo.

W przeciwnym razie jedna wartość jest mniejsza, a druga większa, więc żadne dziecko v nie zawiera obu wartości albo jedna z nich jest równa v, który jest swoim własnym przodkiem. Tak czy inaczej, v jest najniższym węzłem znajdującym się nad obiema wartościami. W trzecim przykładzie 50 jest mniejsze od obu wartości, więc idziesz w prawo do 70, gdzie 55 jest mniejsze, a 80 większe. Jedna para porównań na poziom daje czas O(h) i pamięć O(1).

Algorytm

Zacznij od indeksu i = 0.
Odczytaj v = tree[i].
Jeśli p < v i q < v, przejdź do 2*i+1 i powtórz.
Jeśli p > v i q > v, przejdź do 2*i+2 i powtórz.
W przeciwnym razie zwróć 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

Pułapki i przypadki brzegowe

Używanie ≤ i ≥ w testach ruchu. Przy p = 12 i q = 10 przejście mija 12 i dociera do 10, a następnie zwraca 10 albo wychodzi poza drzewo.
Zakładanie, że p < q. W drugim przykładzie p ma większą wartość. Porównaj obie wartości z węzłem albo najpierw zamień je miejscami.
Zwracanie indeksu zamiast wartości. Odpowiedzią jest tree[i], a nie i.
W Lua i R tablice zaczynają się od indeksu 1. Zachowaj indeksy węzłów liczone od 0 na potrzeby działania 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania3

Jaka jest złożoność czasowa znajdowania najniższego wspólnego przodka w BST?

Przejście od korzenia przebiega jedną ścieżką, więc zajmuje O(h) czasu dla drzewa o głębokości h i O(1) dodatkowej pamięci. W przypadku zrównoważonego drzewa jest to O(log n); w przypadku drzewa przypominającego pojedynczą ścieżkę jest to O(n).

Czym różni się LCA w binarnym drzewie wyszukiwań od LCA w drzewie binarnym?

W zwykłym drzewie binarnym wartość może znajdować się w dowolnym miejscu, więc możesz przeszukać każdy węzeł — to O(n) pracy. W drzewie wyszukiwań porównanie tych dwóch wartości z wartością w węźle wskazuje, po której stronie znajduje się każda z nich, więc podążasz jedną ścieżką od korzenia.

Czy węzeł może być swoim własnym najniższym wspólnym przodkiem?

Tak. Węzeł jest swoim własnym przodkiem, więc gdy p znajduje się wyżej niż q, odpowiedzią jest p, a gdy obie wartości są równe, odpowiedzią jest ta wartość.

def lowestCommonAncestor(tree, p, q):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

Lowest Common Ancestor of a BST

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Przeszukaj całe drzewo, ignorując kolejność

Porównaj dwie ścieżki wyszukiwania

Schodź w dół, aż wartości się rozdzielą

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania