Bottom View of Binary Tree

Q: Jaka jest złożoność czasowa wyznaczania widoku dolnego drzewa binarnego?

O(n) dla n węzłów: wyszukiwanie wszerz obsługuje każdy węzeł raz, wykonując jeden zapis w mapie mieszającej. Uporządkowana mapa, taka jak mapa drzewiasta, dodaje czynnik log w dla w kolumn.

ŚredniePrzechodzenie drzewa Haszowanie

+10

Tablica root przechowuje drzewo binarne: korzeń znajduje się pod indeksem 0, dzieci węzła o indeksie i pod indeksami 2i+1 (lewe) i 2i+2 (prawe), -1 oznacza puste miejsce, a na końcu mogą znajdować się dodatkowe wpisy -1.

Korzeń znajduje się w kolumnie 0; krok w lewo przesuwa o jedną kolumnę w lewo, a krok w prawo o jedną kolumnę w prawo. Patrząc od dołu, w każdej kolumnie widać najgłębszy węzeł, a w przypadku remisu — ostatni na tym poziomie, czytając od lewej do prawej (ten o większym indeksie). Zwróć widoczne wartości, zaczynając od kolumny położonej najbardziej na lewo.

Funkcja

bottomView(root: integer-array) → integer-array

rootinteger-array: drzewo w kolejności kopcowej, z wartością -1 oznaczającą puste miejsce
Zwracainteger-array: wartość widoczna od dołu w każdej kolumnie, zaczynając od lewej

Ograniczenia

1 ≤ root.length ≤ 32767
Każdy element root[i] jest równy -1 lub ma wartość spełniającą warunek 0 ≤ root[i] ≤ 10⁴, a żadna wartość się nie powtarza.
root[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 po ostatnim węźle.
Oboje dzieci pustego miejsca również są puste, a drzewo ma najwyżej 14 poziomów.

Przykłady

Wejście: root = [5, 2, 9, 4, 7, 1, 6]
Wyjście: [4, 2, 1, 9, 6]
Wyjaśnienie: Kolumna 0 zawiera 5 i, dwa poziomy niżej, 7 (indeks 4) oraz 1 (indeks 5). 1 znajduje się później na tym samym poziomie, więc jest widoczne. Kolumny -2, -1, 1 i 2 zawierają 4, 2, 9 i 6.

Wejście: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Wyjście: [5, 4, 3]
Wyjaśnienie: Kolumna -1 zawiera 2, a dwa poziomy niżej 5 (indeks 9), więc widzisz 5. W kolumnie 0 4 znajduje się pod korzeniem. Kolumna 1 zawiera tylko 3.

Wejście: root = [8, -1, -1, -1]
Wyjście: [8]
Wyjaśnienie: Każde miejsce po korzeniu ma wartość -1, więc 8 jest jedynym węzłem, a kolumna 0 jedyną kolumną.

Pytanie dodatkowe

Jeśli przy remisie na najgłębszym poziomie kolumny należy zwrócić wszystkie węzły z remisem, od lewej do prawej, jak należałoby zmienić wersję przeszukiwania wszerz? Co zwróci kolumna 0 w przykładzie 1?

Rozwiązanie

Każda kolumna pokazuje swój najgłębszy węzeł, a przy remisie wygrywa węzeł późniejszy w kolejności poziomami. Przeszukiwanie wszerz odwiedza węzły w kolejności poziomami, więc ostatni odwiedzony węzeł w kolumnie jest odpowiedzią: pozwól, aby każdy węzeł nadpisywał miejsce przypisane swojej kolumnie.

Przeszukiwanie w głąb, najgłębszy węzeł w każdej kolumnie

Intuicja

Przejdź drzewo w głąb, przypisując każdemu węzłowi jego kolumnę i głębokość, a dla każdej kolumny zapisuj głębokość i wartość najgłębszego dotąd węzła.

Odwiedzanie lewego poddrzewa przed prawym sprawia, że napotykasz węzły danego poziomu od lewej do prawej, więc szukany węzeł jest ostatnim napotkanym: zastępuj go, gdy głębokość jest większa lub równa. W przykładzie 1 przejście napotyka 7, a następnie 1, oba na głębokości 2 w kolumnie 0, więc 1 zajmuje tę kolumnę.

Kolumny tworzą jeden nieprzerwany zakres, więc śledź najmniejszą i największą, a następnie odczytaj każdą kolumnę pomiędzy nimi. Jedna wizyta na węzeł oznacza czas O(n), a rekurencja ma głębokość h wywołań dla drzewa o h poziomach.

Algorytm

Odwiedź korzeń z kolumną 0 i głębokością 0.
Pomiń indeks i, gdy wykracza poza koniec tablicy lub root[i] ma wartość -1.
Jeśli kolumna nie ma jeszcze węzła lub ta głębokość jest większa niż albo równa zapisanej, zapisz tę głębokość i wartość.
Odwiedź 2i+1 z kolumną col-1, a następnie 2i+2 z kolumną col+1, oba poziom głębiej.
Zwróć zapisane wartości, zaczynając od najmniejszej kolumny.

def bottomView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the deepest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later in level order.
        if col not in best or depth >= best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Szerokościowo, ostatni węzeł w każdej kolumnie

Intuicja

Kolejka, do której każdy węzeł opuszczający ją dopisuje swoje lewe dziecko, a następnie prawe, zwraca węzły w kolejności poziomami: każdy węzeł o głębokości d przed dowolnym węzłem o głębokości d+1, a w obrębie każdego poziomu od lewej do prawej. Spośród węzłów w danej kolumnie najgłębszy zostanie zwrócony jako ostatni, a przy remisie ten położony bardziej na prawo. Dlatego gdy każdy węzeł nadpisuje wartość przypisaną do swojej kolumny, w każdej kolumnie pozostaje węzeł widziany od dołu, bez potrzeby porównywania głębokości.

W przykładzie 1 węzeł 7 zapisuje wartość w kolumnie 0, a węzeł 1 ją nadpisuje.

Każdy węzeł wymaga jednej wizyty w kolejce i jednego zapisu w mapie: czas O(n). Kolejka może pomieścić cały poziom, czyli około połowę węzłów, więc złożoność pamięciowa wynosi O(n).

Algorytm

Umieść parę (indeks 0, kolumna 0) w kolejce.
Wyjmij parę (i, col) i zapisz root[i] pod col, zastępując każdą wcześniejszą wartość.
Dodaj (2i+1, col-1), a następnie (2i+2, col+1) dla każdego dziecka, które znajduje się w tablicy i nie jest równe -1.
Powtarzaj, aż kolejka będzie pusta, śledząc najmniejszą i największą kolumnę.
Zwróć wartości mapy, zaczynając od najmniejszej kolumny.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

Pułapki i przypadki brzegowe

Zastępowanie w wersji przeszukiwania w głąb tylko wtedy, gdy głębokość jest ściśle większa. W przykładzie 1 pozostaje wtedy 7 zamiast 1.
Zachowanie pierwszego węzła, który przeszukiwanie wszerz napotyka w każdej kolumnie. To widok z góry.
Dodawanie prawego dziecka do kolejki przed lewym. Każdy poziom jest wtedy odwiedzany od prawej do lewej, a przy remisach wybierany jest niewłaściwy węzeł.
Przyjmowanie liści za wynik. W przykładzie 1 liść 7 jest ukryty przez 1, a w przykładzie 2 węzeł 4 ma dziecko, a mimo to jest najniżej położonym węzłem w kolumnie 0.
Sortowanie kolumn jako tekstu. Jako ciąg znaków "-10" trafia między "-1" a "-2".

Najczęstsze pytania3

Co to jest widok od dołu drzewa binarnego?

Przypisz kolumnie głównej wartość 0, każdemu krokowi w lewo o jedną kolumnę mniej, a każdemu krokowi w prawo o jedną więcej. Widok od dołu wyświetla najgłębszy węzeł z każdej kolumny, od lewej do prawej. W tym zadaniu remis pod względem głębokości rozstrzyga kolejność poziomami, wybierając późniejszy węzeł.

Jaka jest złożoność czasowa wyznaczania widoku dolnego drzewa binarnego?

O(n) dla n węzłów: wyszukiwanie wszerz obsługuje każdy węzeł raz, wykonując jeden zapis w mapie mieszającej. Uporządkowana mapa, taka jak mapa drzewiasta, dodaje czynnik log w dla w kolumn.

Jaka jest różnica między widokiem z góry a widokiem z dołu?

Oba wybierają po jednym węźle z każdej kolumny. Widok z góry wybiera węzeł o najmniejszej głębokości, a widok z dołu — o największej. W wersji przeszukiwania wszerz widok z góry zachowuje pierwszą wartość przypisaną do kolumny, a widok z dołu nadpisuje ją za każdym razem.

def bottomView(root):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 4, 7, 1, 6]

Oczekiwany wynik

[4, 2, 1, 9, 6]