Lowest Common Ancestor of a Binary Tree

Q: Czym to się różni od najniższego wspólnego przodka w binarnym drzewie wyszukiwania?

W drzewie wyszukiwania porównanie p i q z węzłem informuje, po której stronie znajduje się każdy z nich, więc jedna ścieżka od korzenia pozwala znaleźć odpowiedź w O(h). Tutaj porównanie niczego nie mówi, więc przeszukujesz poddrzewa.

Q: Czy potrafisz znaleźć najniższego wspólnego przodka, korzystając ze wskaźników do rodzica?

Tak. W tej tablicy rodzicem indeksu i jest (i-1)/2 zaokrąglone w dół. Przesuwaj większy z dwóch indeksów do jego rodzica, aż będą równe; większy indeks nigdy nie jest przodkiem mniejszego. W przypadku połączonych węzłów umieść przodków p w zbiorze i przechodź w górę od q do pierwszego z nich, który się w nim znajduje.

ŚredniePrzechodzenie drzewa Rekurencja

+10

Otrzymujesz drzewo binarne w tablicy root, w porządku kopcowym: korzeń znajduje się pod indeksem 0, dzieci węzła o indeksie i pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), a wartość -1 oznacza puste miejsce. Wartości są różne i nie są uporządkowane.

Zwróć wartość najniższego wspólnego przodka węzłów p i q, czyli dwóch różnych wartości: najgłębiej położonego węzła, którego poddrzewo zawiera oba te węzły. Poddrzewo obejmuje swój wierzchołek, więc jeśli q znajduje się poniżej p, odpowiedzią jest p.

Funkcja

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

rootinteger-array: drzewo binarne w kolejności poziomami, z wartością -1 w pustym miejscu
pinteger: wartość jednego węzła
qinteger: wartość innego węzła
Zwracainteger: wartość najniższego węzła, którego poddrzewo zawiera zarówno p, jak i q

Ograniczenia

2 ≤ root.length ≤ 32767
Każdy element root[i] ma wartość -1 lub wartość spełniającą warunek 0 ≤ root[i] ≤ 10⁴.
root[0] nigdy nie jest -1, a drzewo ma co najmniej dwa węzły.
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 najwyżej 14.
Wszystkie wartości w drzewie są różne i nie są uporządkowane.
p i q to wartości dwóch różnych węzłów w drzewie, w dowolnej kolejności.

Przykłady

Wejście: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Wyjście: 3
Wyjaśnienie: 6 jest lewym dzieckiem 3, a 9 znajduje się poniżej 4, po prawej stronie 3, więc ich wspólnym przodkiem jest 3. Porównanie wartości wskazałoby korzeń 8: 6 jest mniejsze, a 9 większe.

Wejście: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Wyjście: 4
Wyjaśnienie: 7 jest lewym dzieckiem 4, a poddrzewo 4 obejmuje samo 4, więc odpowiedzią jest 4.

Wejście: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Wyjście: 6
Wyjaśnienie: Korzeń 1 nie ma lewego dziecka. Jego prawe dziecko 6 ma po lewej stronie 3, a po prawej 0, więc wartości spotykają się przy 6.

Pytanie dodatkowe

Jeśli p lub q może nie występować, a odpowiedzią jest -1, który skrót w pojedynczym przebiegu przestaje działać i jak mimo to ukończyć zadanie podczas jednego przejścia?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Żadna kolejność nie podpowiada, po której stronie znajduje się wartość, więc musisz to sprawdzić. Jedno przejście w porządku postorder pozwala każdemu poddrzewu zgłosić, co znalazło, a wartości spotykają się w pierwszym węźle, który otrzyma informacje z obu stron.

Idź w dół, przeszukując każdą stronę

Intuicja

Schodź w dół od korzenia i przy każdym węźle szukaj w lewym poddrzewie p oraz q. Jeśli są tam oba: idź w lewo. Jeśli nie ma żadnego: idź w prawo. Jeśli jest po jednym: wartości się rozdzielają i ten węzeł jest odpowiedzią. Węzeł zawierający p lub q również jest odpowiedzią, ponieważ druga wartość musi znajdować się poniżej niego. Dla 6 i 9 korzeń znajduje obie wartości po swojej lewej stronie, a w węźle 3 samotne 6 zawiera tylko p.

Każdy krok w dół przeszukuje całe poddrzewo, więc h poziomów kosztuje O(n·h), a w wysokim, wąskim drzewie bez ograniczenia głębokości — O(n²). Wyszukiwanie w węźle 8 odwiedziło już każdy węzeł poniżej 3, a krok w węźle 3 ponownie odwiedza niektóre z nich.

Algorytm

Zapisz contains(i, value): false dla pustego miejsca (za końcem lub -1), true, jeśli root[i] jest równe value, w przeciwnym razie sprawdź oboje dzieci.
Zacznij od i = 0. Jeśli root[i] to p lub q, zwróć tę wartość.
Jeśli lewe poddrzewo pod 2*i+1 zawiera obie wartości, przejdź tam. Jeśli nie zawiera żadnej z nich, przejdź do 2*i+2.
W przeciwnym razie zwróć 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 side

Jedno przejście postorderowe

Intuicja

Niech każde poddrzewo odpowie raz, od dołu do góry. find(i) zwraca indeks wspólnego przodka, jeśli poddrzewo w węźle i zawiera obie wartości, indeks p lub q, jeśli zawiera jedną z nich, oraz -1, jeśli nie zawiera żadnej.

Węzeł zawierający p lub q zwraca własny indeks, nie sprawdzając niższych poziomów. Jeśli druga wartość znajduje się w jego poddrzewie, ten węzeł jest wspólnym przodkiem; jeśli nie, węzeł wyżej otrzymuje informację z obu stron. Każdy inny węzeł pyta oboje dzieci. Dwa wyniki oznaczają, że wartości dotarły z różnych stron i spotykają się tutaj. Pojedynczy wynik jest przekazywany wyżej bez zmian, niezależnie od tego, czy dotyczy jednej wartości, czy jest już gotową odpowiedzią.

W pierwszym przykładzie węzeł 3 otrzymuje indeks 3 z lewej strony i 10 z prawej, zwraca własny indeks 1, a korzeń przekazuje go wyżej. Każdy węzeł jest odwiedzany raz: czas O(n), rekurencja O(h).

Algorytm

find(i) zwraca -1 dla indeksu wykraczającego poza koniec lub dla wartości -1.
Węzeł, którego wartością jest p lub q, zwraca i bez sprawdzania niższych poziomów.
Każdy inny węzeł oblicza left = find(2*i+1) i right = find(2*i+2). Jeśli żadne z nich nie jest -1, zwraca i; w przeciwnym razie zwraca to, które nie jest -1, albo -1.
Zwróć 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)]

Pułapki i przypadki brzegowe

Porównywanie wartości z węzłem. Drzewo nie jest uporządkowane: w pierwszym przykładzie przechodzenie kończy się na korzeniu 8 zamiast 3.
Przekazywanie w górę true lub false zamiast indeksu. Rodzic nie może stwierdzić, czy gotowa odpowiedź znajduje się już poniżej.
Odczytywanie dziecka bez sprawdzenia długości. 9 pod indeksem 10 ma indeksy dzieci 21 i 22, które wykraczają poza ostatni element.
Zwracanie find(0), czyli indeksu, zamiast root[find(0)].
W Lua i R tablice zaczynają się od 1: zachowaj indeksy węzłów liczone od 0 i odczytuj root[i + 1].

Najczęstsze pytania3

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

Przejście postorder odwiedza każdy węzeł co najwyżej raz: czas O(n). Stos rekurencji przechowuje jedną ramkę na poziom, więc zapotrzebowanie na pamięć wynosi O(log n) w przypadku zrównoważonego drzewa i O(n) w przypadku drzewa o kształcie ścieżki.

Czym to się różni od najniższego wspólnego przodka w binarnym drzewie wyszukiwania?

W drzewie wyszukiwania porównanie p i q z węzłem informuje, po której stronie znajduje się każdy z nich, więc jedna ścieżka od korzenia pozwala znaleźć odpowiedź w O(h). Tutaj porównanie niczego nie mówi, więc przeszukujesz poddrzewa.

Czy potrafisz znaleźć najniższego wspólnego przodka, korzystając ze wskaźników do rodzica?

Tak. W tej tablicy rodzicem indeksu i jest (i-1)/2 zaokrąglone w dół. Przesuwaj większy z dwóch indeksów do jego rodzica, aż będą równe; większy indeks nigdy nie jest przodkiem mniejszego. W przypadku połączonych węzłów umieść przodków p w zbiorze i przechodź w górę od q do pierwszego z nich, który się w nim znajduje.

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

Test #1

Test #2

Test #3

Argumenty

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

Oczekiwany wynik