Lowest Common Ancestor of a BST

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

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

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

W zwykłym drzewie binarnym wartość może znajdować się w dowolnym miejscu, dlatego przeszukujesz oba poddrzewa każdego węzła, a złożoność wynosi O(n) . W drzewie wyszukiwań porównanie obu 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. Rekurencyjna metoda dla dowolnego drzewa nadal działa w drzewie wyszukiwań, ale nie wykorzystuje tych informacji.

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ę nad q , odpowiedzią jest p . Ta sama zasada daje p , gdy obie wartości są równe. Przejście obsługuje oba przypadki: zatrzymuje się, gdy tylko bieżący węzeł jest równy jednej z wartości.

Q: Dlaczego przejście zatrzymuje się przy pierwszym węźle, w którym p i q się rozchodzą?

W tym węźle jedna wartość jest mniejsza, a druga większa, więc znajdują się w różnych poddrzewach. Każdy węzeł poniżej niego znajduje się tylko w jednym z tych poddrzew i nie może zawierać obu wartości. Węzeł rozdzielający zawiera obie wartości i żaden węzeł położony głębiej ich nie zawiera, co dokładnie odpowiada definicji najniższego wspólnego przodka.

ŚrednieDrzewo BST

+10

Otrzymujesz binarne drzewo wyszukiwań zapisane w tablicy tree w porządku poziomami oraz dwie wartości p i q, które obie w nim występują. 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), -1 oznacza puste miejsce, a tablica może kończyć się dodatkowymi wpisami -1. W binarnym drzewie wyszukiwań każda wartość w lewym poddrzewie węzła jest mniejsza od wartości węzła, a każda wartość w jego prawym poddrzewie jest większa.

Napisz funkcję o nazwie lowestCommonAncestor, która zwraca wartość najniższego wspólnego przodka węzłów p i q: najgłębszego węzła, który ma oba z nich w swoim poddrzewie. Węzeł jest uznawany za część własnego poddrzewa, więc jeśli p znajduje się wyżej niż q, odpowiedzią jest samo p.

Funkcja

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

treeinteger-array: drzewo wyszukiwań binarnych 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żdy element tree[i] ma wartość -1 lub wartość spełniającą warunek 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 poprawnym drzewem przeszukiwań binarnych, 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ć sobie 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: 3 jest lewym dzieckiem 8, a 15 znajduje się poniżej 12, po prawej stronie 8. Wspinając się od każdego z nich w górę, pierwszym węzłem, do którego docierają oba, jest 8, więc to jest odpowiedź; 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. Węzeł jest swoim własnym przodkiem, więc 12 ma w swoim poddrzewie obie wartości, a żaden węzeł poniżej niego ich nie ma: odpowiedzią jest 12. Wartości mogą występować w dowolnej kolejności; tutaj p jest większą z nich.

Wejście: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Wyjście: 70
Wyjaśnienie: Zarówno 55, jak i 80 są większe niż korzeń 50, więc oba znajdują się po jego prawej stronie. Przy 70 ich drogi się rozchodzą: 55 jest mniejsze i znajduje się po lewej stronie (poniżej 60), a 80 jest większe i znajduje się po prawej stronie. Zatem odpowiedzią jest 70.

+12 ukrytych testów przy wysłaniu

Pytanie dodatkowe

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

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

W zwykłym drzewie binarnym nie da się stwierdzić, gdzie znajduje się dana wartość, bez przeszukania obu stron każdego węzła. Drzewo wyszukiwań podpowiada ci przy każdym węźle: mniejsze wartości są po lewej, a większe po prawej. Zacznij więc od korzenia i przechodź w stronę, po której znajdują się obie wartości. Pierwszy węzeł, przy którym przestają znajdować się po tej samej stronie, jest odpowiedzią. Znajdziesz go, podążając jedną ścieżką, bez zaglądania do reszty drzewa.

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

Intuicja

Najpierw: jak poruszać się po tablicy. Węzeł o indeksie i ma lewe dziecko pod indeksem 2*i+1, a prawe dziecko pod indeksem 2*i+2. Dziecko istnieje tylko wtedy, gdy jego indeks mieści się w tablicy, a wartość pod tym indeksem nie jest równa -1. W tablicy [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] korzeń 20 ma dzieci 8 i 31 pod indeksami 1 i 2, a węzeł 12 pod indeksem 4 ma dzieci 10 i 15 pod indeksami 9 i 10.

Ta pierwsza metoda działa dla dowolnego drzewa binarnego. Rekurencyjna funkcja find(i) zwraca informację o tym, co zawiera poddrzewo pod indeksem i. Puste miejsce zwraca -1. Węzeł zawierający p lub q zwraca sam siebie: albo druga wartość znajduje się niżej i wtedy ten węzeł jest odpowiedzią, albo druga wartość jest gdzie indziej i wtedy węzeł położony wyżej zobaczy obie. W przeciwnym razie węzeł pyta oboje dzieci. Jeśli obie strony coś zwracają, p znajduje się po jednej stronie, a q po drugiej, więc ten węzeł jest miejscem, w którym się spotykają. Jeśli coś zwraca tylko jedna strona, przekaż tę wartość wyżej.

Dla p = 3 i q = 15 węzeł 8 otrzymuje indeks 3 z lewej strony i indeks 10 z prawej, więc zwraca sam siebie. Korzeń otrzymuje tę wartość z lewej strony i -1 z prawej, po czym przekazuje 8 wyżej.

Metoda jest poprawna, ale może odwiedzić każdy węzeł, co zajmuje O(n) czasu, a rekurencja wymaga O(h) miejsca. Nie wykorzystuje kolejności wartości, która jest przecież najważniejszą cechą drzewa wyszukiwań.

Algorytm

Napisz find(i). Jeśli miejsce pod i jest puste (poza końcem lub -1), zwróć -1.
Jeśli tree[i] to p lub q, zwróć i.
Wywołaj find dla 2*i+1 i 2*i+2. Jeśli oba wywołania coś znalazły, zwróć i.
W przeciwnym razie zwróć wynik tej strony, która coś znalazła, lub -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

Teraz wykorzystaj kolejność. Wartość możesz znaleźć tak, jak przeszukuje się drzewo wyszukiwań: zacznij od korzenia, idź w lewo, gdy wartość jest mniejsza od wartości w węźle, w prawo, gdy jest większa, i zatrzymaj się, gdy ją znajdziesz. Ta ścieżka przechodzi przez wszystkich przodków tej wartości i przez nic więcej, ponieważ ścieżka od korzenia do węzła jest unikalna.

Zapisz ścieżkę dla p i ścieżkę dla q. Obie zaczynają się od korzenia i prowadzą przez te same węzły, dopóki wartości nie skierują ich w różne strony. Wspólny początek to lista ich wspólnych przodków, więc ostatnia wspólna wartość jest najniższa. Dla 3 i 15 ścieżki to 20, 8, 3 i 20, 8, 12, 15: mają wspólne 20, 8, a odpowiedzią jest 8. Dla 12 i 10 są to 20, 8, 12 i 20, 8, 12, 10, a odpowiedzią jest 12.

Każda ścieżka wymaga jednego kroku na poziom, więc czas działania wynosi O(h), tutaj najwyżej 14 kroków, niezależnie od liczby węzłów w drzewie. Dwie listy zajmują O(h) pamięci.

Algorytm

Napisz path(target): zacznij od indeksu 0, zapisz tree[i], zakończ, gdy będzie równe target, w przeciwnym razie przejdź do 2*i+1, jeśli target jest mniejsze, a do 2*i+2, jeśli jest większe.
Zbuduj ścieżkę do p i ścieżkę do q.
Przechodź obie listy od początku, dopóki ich wartości są zgodne, zapamiętując ostatnią zgodną wartość.
Zwróć tę ostatnią wspólną 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, dopóki p i q poruszają się w tym samym kierunku, więc nie musisz ich zapisywać. Podążaj obiema jednocześnie. W węźle zawierającym v, jeśli obie wartości są mniejsze niż v, 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 dotarłeś do celu. Albo jedna wartość jest mniejsza niż v, a druga większa, więc znajdują się w różnych poddrzewach i żadne dziecko v nie zawiera obu; albo jedna z nich jest równa v, a węzeł jest swoim własnym przodkiem. W obu przypadkach v jest najgłębszym węzłem nad obiema wartościami.

W trzecim przykładzie korzeń 50 jest mniejszy od 55 i 80, więc przechodzisz w prawo do 70. Tam 55 jest mniejsze, a 80 większe: odpowiedzią jest 70. W drugim przykładzie przechodzisz od 20 do 8, a następnie do 12, które jest równe p, i zatrzymujesz się.

Podążasz pojedynczą ścieżką od korzenia, wykonując jedną parę porównań na każdym poziomie, więc złożoność czasowa wynosi O(h), a złożoność pamięciowa O(1). Pozostała część drzewa nigdy nie jest odczytywana.

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

Ścieżka jest krótka, więc większość błędów wynika z warunku jej zakończenia.

Używanie ≤ i ≥ w testach ruchu. Przy p = 12 i q = 10 test p ≤ 12 i q ≤ 12 prowadzi poza odpowiedź, do 10, a stamtąd ścieżka zwraca 10 albo wychodzi poza drzewo. Wykonuj ruch tylko wtedy, gdy obie wartości leżą ściśle po tej samej stronie.
Zakładanie, że p < q. Wartości mogą pojawić się w dowolnej kolejności. Porównaj obie z węzłem albo najpierw je zamień, tak aby p było mniejsze.
Zapominanie, że jedna wartość może być przodkiem drugiej. W takim przypadku odpowiedzią jest sama ta wartość, a nie jej rodzic.
Zwracanie indeksu zamiast wartości. Funkcja zwraca tree[i], a nie i.
Przeszukiwanie całego drzewa. Daje poprawną odpowiedź, ale odwiedza nawet każdy węzeł, choć wystarczy przejść jedną ścieżkę.
Pomylenie przesunięcia w Lua i R, gdzie tablice zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 dla działania 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania4

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

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

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

W zwykłym drzewie binarnym wartość może znajdować się w dowolnym miejscu, dlatego przeszukujesz oba poddrzewa każdego węzła, a złożoność wynosi O(n). W drzewie wyszukiwań porównanie obu 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. Rekurencyjna metoda dla dowolnego drzewa nadal działa w drzewie wyszukiwań, ale nie wykorzystuje tych informacji.

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ę nad q, odpowiedzią jest p. Ta sama zasada daje p, gdy obie wartości są równe. Przejście obsługuje oba przypadki: zatrzymuje się, gdy tylko bieżący węzeł jest równy jednej z wartości.

Dlaczego przejście zatrzymuje się przy pierwszym węźle, w którym p i q się rozchodzą?

W tym węźle jedna wartość jest mniejsza, a druga większa, więc znajdują się w różnych poddrzewach. Każdy węzeł poniżej niego znajduje się tylko w jednym z tych poddrzew i nie może zawierać obu wartości. Węzeł rozdzielający zawiera obie wartości i żaden węzeł położony głębiej ich nie zawiera, co dokładnie odpowiada definicji najniższego wspólnego przodka.

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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 pytania4

Podobne zadania