Left View of Binary Tree

+10

Otrzymujesz drzewo binarne jako tablicę root w kolejności kopcowej: 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. Tablica może kończyć się dodatkowymi wpisami -1.

Stań po lewej stronie drzewa. Na każdym poziomie widzisz jeden węzeł — ten najbardziej po lewej; pozostałe węzły na tym poziomie są za nim ukryte. Zwróć widoczne wartości, od najwyższego poziomu w dół.

Funkcja

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

rootinteger-array: drzewo w kolejności kopcowej, z wartością -1 w pustym miejscu
Zwracainteger-array: skrajna lewa wartość każdego poziomu, zaczynając od najwyższego

Ograniczenia

1 ≤ root.length ≤ 32767
Każde root[i] ma wartość -1 lub wartość z zakresu 0 ≤ root[i] ≤ 10⁴.
Wartości węzłów są różne.
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 za ostatnim węzłem.
Oba węzły potomne pustego pola również są puste, a drzewo ma co najwyżej 14 poziomów.

Przykłady

Wejście: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Wyjście: [3, 8, 6, 1]
Wyjaśnienie: 8 jest liściem, więc na trzecim i czwartym poziomie znajdują się tylko 6 (indeks 6) i 1 (indeks 13), oba pod prawym dzieckiem 5. I tak je widzisz: [3, 8, 6, 1].

Wejście: root = [10, -1, -1]
Wyjście: [10]
Wyjaśnienie: Indeksy 1 i 2 zawierają -1, więc 10 nie ma dzieci, a widok zawiera tylko korzeń.

Wejście: root = [1, 2, 3, 4, 5, 6, 7]
Wyjście: [1, 2, 4]
Wyjaśnienie: Pełne drzewo o trzech poziomach. Skrajne lewe miejsca na poziomach mają indeksy 0, 1 i 3, które zawierają 1, 2 i 4.

Pytanie dodatkowe

Poziom d wypełnia indeksy od 2^d-1 do 2^(d+1)-2. Czy potrafisz zbudować widok, przeglądając te zakresy, bez kolejki ani rekurencji? Jaki jest koszt w przypadku dopełnionej tablicy?

Rozwiązanie

Podążanie do lewych dzieci od korzenia kończy się niepowodzeniem, gdy lewe poddrzewo jest krótsze: w pierwszym przykładzie niższe poziomy są widoczne przez prawe poddrzewo. Potrzebujesz pierwszego węzła na każdym poziomie. Wyszukiwanie wszerz podaje węzły każdego poziomu od lewej do prawej; przejście w głąb, które najpierw odwiedza lewe węzły, jako pierwsze napotyka najbardziej lewy węzeł każdego poziomu.

Wszerz, pierwszy węzeł każdego poziomu

Intuicja

Kolejka przetwarzana rundami podaje kolejne poziomy, po jednym na raz. Na początku rundy kolejka zawiera dokładnie jeden poziom, od lewej do prawej, ponieważ każde dziecko dodane w trakcie rundy trafia za nim. Wyjmij tyle indeksów, ile wynosi liczba elementów na poziomie, dodawaj dzieci każdego z nich do kolejki, zaczynając od lewego, i zachowaj pierwszą wartość.

W pierwszym przykładzie rundy to [3], [8, 5], [6] i [1], a zachowane wartości to 3, 8, 6 i 1. 8 niczego nie dodaje, ponieważ w miejscach jego dzieci, 3 i 4, znajduje się -1.

Każdy węzeł trafia do kolejki i ją opuszcza tylko raz: czas O(n). Kolejka przechowuje cały poziom, czyli do 8192 indeksów w pełnym drzewie o 14 poziomach.

Algorytm

Utwórz kolejkę zawierającą indeks 0 i pustą odpowiedź.
Dopóki kolejka nie jest pusta, przyjmij, że s oznacza jej rozmiar, i usuń s indeksów. Dołącz wartość pierwszego z nich.
Dla każdego usuniętego indeksu i dodaj do kolejki 2i+1, a następnie 2i+2, pomijając indeksy wykraczające poza koniec oraz wpisy równe -1.

from collections import deque


def leftView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == 0:
                view.append(root[i])  # the first node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

W głąb, najpierw lewe dziecko

Intuicja

Przechodź drzewo w głąb, najpierw lewe poddrzewo, a potem prawe, i przekazuj głębokość każdego węzła. Pierwszy węzeł, do którego dojdziesz na głębokości d, jest najbardziej lewy na poziomie d. Weź najbardziej lewy węzeł x na danym poziomie oraz dowolny węzeł y po jego prawej stronie: w ostatnim węźle, którego ścieżki mają wspólny przebieg, x skręca w lewo, a y w prawo, a przejście kończy lewą gałąź, zanim skręci w prawo.

Przejście schodzi o jeden poziom naraz, więc gdy po raz pierwszy dociera do głębokości d, odpowiedź zawiera dokładnie d wartości. Zapisuj węzeł, gdy d jest równe długości odpowiedzi; nie jest potrzebny zbiór odwiedzonych głębokości.

Każdy węzeł jest odwiedzany raz, czas działania wynosi O(n), a pamięć przechowuje jedno wywołanie na poziom, maksymalnie 14 w tym przypadku. Wersja R utrzymuje własny stos i umieszcza prawe dziecko przed lewym.

Algorytm

Utwórz pustą odpowiedź i wywołaj visit(0, 0).
W visit(i, d) od razu zakończ, jeśli i znajduje się poza tablicą lub root[i] ma wartość -1.
Jeśli d jest równe długości odpowiedzi, przejście po raz pierwszy dotarło do poziomu d: dodaj root[i].
Wywołaj visit(2i+1, d+1), a następnie visit(2i+2, d+1).
Zwróć odpowiedź po zakończeniu pierwszego wywołania.

def leftView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Pułapki i przypadki brzegowe

Podążanie wyłącznie za lewymi dziećmi od korzenia. W pierwszym przykładzie kończy się to na 8 i pomija 6 oraz 1.
Odczytywanie pierwszego miejsca na każdym poziomie, root[2^d-1]. W pierwszym przykładzie pierwsze miejsce na trzecim poziomie, indeks 3, zawiera -1, podczas gdy jedyny węzeł tego poziomu znajduje się pod indeksem 6.
Odwiedzanie prawego dziecka jako pierwszego podczas przechodzenia w głąb. Pierwszy napotkany węzeł na każdym poziomie jest wtedy najbardziej wysunięty w prawo.
Odczytywanie dziecka bez sprawdzania granic. 1 pod indeksem 13 ma miejsca na dzieci 27 i 28, które wykraczają poza koniec 14-elementowej tablicy.

Najczęstsze pytania3

Czy lewy widok jest taki sam jak lewa granica drzewa?

Nie. Lewa granica to ścieżka: zaczyna się od lewego dziecka korzenia, skręca w lewo, jeśli może, w przeciwnym razie w prawo, i kończy się przed liściem. Widok z lewej strony pokazuje jeden węzeł na każdym poziomie z dowolnej gałęzi. W pierwszym przykładzie granica jest pusta, ponieważ 8 jest liściem, ale widok pokazuje 8, 6 i 1.

Jaka jest złożoność czasowa i pamięciowa widoku z lewej strony?

Oba rozwiązania odwiedzają każdy węzeł jeden raz, więc złożoność czasowa wynosi O(n). Kolejka przeszukiwania wszerz przechowuje cały poziom, czyli około połowę węzłów pełnego drzewa. Przejście najpierw w lewo przechowuje jedno wywołanie na poziom, czyli O(h) dla h poziomów.

Jak zmienić rozwiązanie, aby uzyskać prawidłowy widok?

W wersji przeszukiwania wszerz zachowaj ostatnią wartość z każdej rundy zamiast pierwszej. W wersji przeszukiwania w głąb odwiedź prawe dziecko przed lewym; pierwszym węzłem, do którego dociera przejście na każdym poziomie, jest wtedy węzeł skrajnie prawy.

def leftView(root):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Oczekiwany wynik

[3, 8, 6, 1]