Top View of Binary Tree

Q: Jaka jest złożoność czasowa widoku z góry drzewa binarnego?

Przeszukiwanie wszerz odwiedza każdy z n węzłów raz, wykonując jedno wyszukiwanie w mapie w czasie O(1) dla każdego węzła, więc działa w czasie O(n) , jeśli śledzisz najmniejszą i największą kolumnę. Uporządkowana mapa kolumn sprawia, że złożoność wynosi O(n log w) dla w kolumn.

ŚredniePrzechodzenie drzewa Haszowanie

+10

Otrzymujesz drzewo binarne zapisane 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.

Korzeń znajduje się w kolumnie 0; lewe dziecko jest o jedną kolumnę na lewo od rodzica, a prawe — o jedną kolumnę na prawo. Patrząc z góry, widzisz najpłytszy węzeł w każdej kolumnie; w przypadku remisu wybierz ten, który jako pierwszy występuje na swoim poziomie, licząc od lewej do prawej (ma mniejszy indeks). Zwróć widoczne wartości, od skrajnej lewej kolumny do skrajnej prawej.

Funkcja

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

rootinteger-array: drzewo w porządku kopca, z -1 w pustym miejscu
Zwracainteger-array: wartość widziana z góry w każdej kolumnie, zaczynając od skrajnej lewej kolumny

Ograniczenia

1 ≤ root.length ≤ 32767
Każde root[i] jest równe -1 lub ma wartość spełniającą warunek 0 ≤ root[i] ≤ 10⁴, a żadna wartość się nie powtarza.
root[0] nigdy nie jest -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 drzewo ma najwyżej 14 poziomów.

Przykłady

Wejście: root = [5, 2, 9, 4, 7, 1, 6]
Wyjście: [4, 2, 5, 9, 6]
Wyjaśnienie: Kolumny od lewej do prawej zawierają 4 (kolumna -2), 2 (-1), korzeń 5 (0), 9 (1) i 6 (2). 7 i 1 również znajdują się w kolumnie 0, ale korzeń jest nad nimi.

Wejście: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Wyjście: [2, 1, 4]
Wyjaśnienie: 2 znajduje się w kolumnie -1. Jego prawe dziecko 3 o indeksie 4 wraca do kolumny 0, pod korzeń, więc jest ukryte. 4 o indeksie 10, prawe dziecko 3, znajduje się samotnie w kolumnie 1.

Wejście: root = [6, -1, -1]
Wyjście: [6]
Wyjaśnienie: Indeksy 1 i 2 zawierają -1, więc 6 znajduje się samodzielnie w kolumnie 0 i stanowi cały widok.

Pytanie dodatkowe

Zamiast tablicy mamy obiekty węzłów, więc nie ma indeksu, który rozstrzygałby remis. Jak sformułujesz zasadę rozstrzygania remisów i czy zmieni się Twój kod przeszukiwania wszerz?

Rozwiązanie

Każda kolumna pokazuje swój węzeł położony najpłycej, a w przypadku remisu — ten, który występuje pierwszy w porządku poziomami. To dokładnie kolejność, w jakiej wyszukiwanie wszerz odwiedza węzły, więc odpowiedzią jest pierwszy napotkany przez nie węzeł w danej kolumnie. Przejście w głąb również działa, ale wymaga śledzenia głębokości i starannego rozstrzygania remisów.

Przeszukiwanie w głąb, najpłytszy węzeł w każdej kolumnie

Intuicja

Przejdź przez drzewo w głąb, zapisując dla każdego węzła jego kolumnę i głębokość, a dla każdej kolumny przechowuj głębokość i wartość najpłycej położonego dotąd węzła.

Zastępuj wartość tylko przy ściśle mniejszej głębokości. Spośród dwóch węzłów o tej samej głębokości pierwszy w kolejności poziomami zostanie osiągnięty jako pierwszy podczas przejścia, które odwiedza każde lewe poddrzewo przed odpowiadającym mu prawym, ponieważ w miejscu rozgałęzienia ścieżek wybiera lewą stronę. Zastępowanie wartości przy równej głębokości sprawia, że wygrywa późniejszy węzeł: gdy indeks 3 jest pusty, a węzły znajdują się pod indeksami 19 i 23, oba leżą w kolumnie -2 na głębokości 4, a odpowiedzią jest węzeł pod indeksem 19.

Zajęte kolumny tworzą jeden nieprzerwany zakres, ponieważ węzeł w kolumnie -3 ma przodków w kolumnach -1 i -2, więc śledź najmniejszą i największą kolumnę. Każdy węzeł jest odwiedzany raz, co zajmuje O(n) czasu, a rekurencja ma głębokość około h wywołań.

Algorytm

Odwiedź korzeń z kolumną 0 i głębokością 0. Natychmiast wróć, jeśli indeks znajduje się poza tablicą lub zawiera -1.
Jeśli kolumna nie ma jeszcze węzła lub ta głębokość jest ściśle mniejsza od zapisanej, zapisz tę głębokość i wartość.
Odwiedź 2i+1 z kolumną col-1, a następnie 2i+2 z kolumną col+1, o jeden poziom głębiej.
Zwróć zapisane wartości od najmniejszej kolumny do największej.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first 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, pierwszy węzeł w każdej kolumnie

Intuicja

Kolejka, która pobiera korzeń, a następnie lewe dziecko każdego węzła i jego prawe dziecko, 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 na każdym poziomie od lewej do prawej. Taki jest priorytet zadania, więc pierwszy węzeł, który otrzyma kolumna, to ten widziany z góry, a każdy kolejny jest pomijany.

Każdy węzeł wymaga jednego wyszukania w mapie, co łącznie daje O(n). Kolejka może pomieścić cały poziom, czyli do około połowy 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). Jeśli mapa nie zawiera wpisu dla col, zapisz tam root[i].
Dodaj (2i+1, col-1), a następnie (2i+2, col+1) dla każdego istniejącego dziecka.
Gdy kolejka będzie pusta, zwróć wartości mapy od najmniejszej kolumny do największej.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first 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 shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[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 [top[col] for col in range(min(top), max(top) + 1)]

Pułapki i przypadki brzegowe

Zachowanie pierwszego znalezionego węzła podczas przejścia w głąb. Jeśli lewe dziecko korzenia ma prawe dziecko, które ma prawe dziecko (kolumna 1, głębokość 3), przejście napotka je przed prawym dzieckiem korzenia (kolumna 1, głębokość 1).
Dodawanie prawego dziecka do kolejki jako pierwszego: remisy rozstrzygane są na korzyść niewłaściwego węzła.
Sortowanie kolumn jako tekstu: "-1" jest sortowane przed "-2".
Zakładanie, że lewe poddrzewo wypełnia ujemne kolumny. W przykładzie 2 węzeł 4 znajduje się w lewym poddrzewie korzenia i w kolumnie 1.

Najczęstsze pytania3

Czym jest widok z góry drzewa binarnego?

Ponumeruj kolumny, zaczynając od korzenia od 0, o jeden mniej dla lewego dziecka i o jeden więcej dla prawego dziecka. Widok z góry przedstawia dla każdej kolumny, od lewej do prawej, węzeł położony najbliżej korzenia.

Jaka jest złożoność czasowa widoku z góry drzewa binarnego?

Przeszukiwanie wszerz odwiedza każdy z n węzłów raz, wykonując jedno wyszukiwanie w mapie w czasie O(1) dla każdego węzła, więc działa w czasie O(n), jeśli śledzisz najmniejszą i największą kolumnę. Uporządkowana mapa kolumn sprawia, że złożoność wynosi O(n log w) dla w kolumn.

Czym widok z góry różni się od widoku z lewej strony i widoku od dołu?

Widok z lewej strony wybiera pierwszy węzeł na każdym poziomie. Widok z góry wybiera węzeł położony najwyżej w każdej kolumnie. Widok z dołu wybiera najgłębiej położony węzeł w każdej kolumnie, więc przeszukiwanie wszerz nadpisuje każdy węzeł w kolumnie zamiast zachowywać pierwszy.

def topView(root):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

[4, 2, 5, 9, 6]