Binary Tree Level Order Traversal

Q: Jaka jest złożoność czasowa przechodzenia przez drzewo binarne poziomami?

Oba rozwiązania odwiedzają każdy węzeł raz: czas O(n) dla n węzłów. Odpowiedź zawiera n wartości, więc zajętość pamięci wynosi O(n) . Poza tym kolejka przechowuje mniej więcej tyle elementów, ile jest na najszerszym poziomie, a rekurencja — tyle, ile wynosi wysokość drzewa.

Q: Skąd wiadomo, gdzie kończy się jeden poziom w przeszukiwaniu wszerz?

Odczytaj rozmiar kolejki na początku każdej rundy i pobierz dokładnie tyle węzłów. Działają też dwa inne sposoby: przechowuj bieżący poziom i następny poziom na dwóch osobnych listach albo po każdym poziomie dodawaj do kolejki znacznik.

Q: Tablica jest już przechowywana poziom po poziomie. Dlaczego nie odczytać jej fragmentami?

W tym formacie działa to tak: poziom d , z korzeniem na pozycji 0, wypełnia indeksy od 2^d-1 do 2^(d+1)-2 , więc zbieraj niepuste wartości z każdego zakresu, aż trafisz na zakres bez żadnych wartości. Na rozmowach kwalifikacyjnych zwykle przekazuje się obiekty węzłów ze wskaźnikami, a do tego formatu można przenieść tylko kolejkę.

ŚredniePrzechodzenie drzewa Kolejka

+10

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

Zwróć wartości węzłów poziomami: jedną listę dla każdego poziomu, od korzenia do najgłębszego poziomu, z wartościami uporządkowanymi od lewej do prawej.

Funkcja

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: drzewo w porządku kopcowym, z wartością -1 oznaczającą puste miejsce
Zwracainteger-2d-array: jedna lista wartości na poziom, najpierw najwyższy poziom, każda od lewej do prawej

Ograniczenia

1 ≤ tree.length ≤ 32767
Każdy element tree[i] to -1 lub wartość spełniająca warunek 0 ≤ tree[i] ≤ 1000.
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 po ostatnim węźle.
Oboje dzieci pustego miejsca również są puste, a głębokość wynosi co najwyżej 14.

Przykłady

Wejście: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Wyjście: [[4], [9, 2], [6, 8, 5], [3]]
Wyjaśnienie: Indeks 3 jest pusty, więc 9 ma tylko prawe dziecko: 6. Na trzecim poziomie znajdują się 6, 8, 5, a 3 pod indeksem 9, poniżej 6, jest samotnie na czwartym poziomie.

Wejście: tree = [7, -1, -1]
Wyjście: [[7]]
Wyjaśnienie: Oba dzieci korzenia mają wartość -1, więc drzewo składa się z pojedynczego węzła 7 i ma jeden poziom.

Wejście: tree = [1, 3, -1, 5, -1, -1, -1]
Wyjście: [[1], [3], [5]]
Wyjaśnienie: Każdy węzeł ma tylko lewe dziecko: 3 na indeksie 1 i 5 na indeksie 3. Każdy poziom zawiera jedną wartość, a końcowe wpisy -1 niczego nie dodają.

Pytanie dodatkowe

Czy możesz zwrócić poziomy w kolejności zygzakowatej: pierwszy od lewej do prawej, drugi od prawej do lewej i tak dalej, bez sortowania żadnego poziomu?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każdy poziom musi być osobną listą uporządkowaną od lewej do prawej. Przeszukiwanie wszerz z użyciem kolejki odwiedza węzły w tej kolejności, a na początku każdej rundy kolejka zawiera dokładnie jeden poziom, więc jej rozmiar wskazuje, ile węzłów należy pobrać. Sprawdzi się też przechodzenie w głąb, które śledzi głębokość każdego węzła.

Wgłąb w pierwszej kolejności, pogrupowane według głębokości

Intuicja

Przejdź po drzewie w głąb, przekazując każdemu węzłowi jego głębokość: 0 dla korzenia, i zachowaj jedną listę dla każdej głębokości. Węzeł na głębokości d dopisuje swoją wartość do listy d, tworząc tę listę, jeśli jest pierwszym węzłem odwiedzonym na tym poziomie.

Elementy każdej listy pojawiają się od lewej do prawej, ponieważ podczas przejścia najpierw odwiedza się lewe poddrzewo węzła, a dopiero potem prawe. Spośród dwóch węzłów na tym samym poziomie jako pierwszy zostanie osiągnięty ten, którego ścieżka skręca w lewo w miejscu, w którym ścieżki się rozchodzą. W przykładzie 1 kolejność odwiedzin 4, 9, 6, 3, 2, 8, 5 tworzy listy [4], [9, 2], [6, 8, 5], [3].

Każdy węzeł jest odwiedzany raz: czas działania O(n), a głębokość rekurencji jest równa głębokości drzewa, maksymalnie 14 poziomów.

Algorytm

Utwórz pustą listę poziomów.
Odwiedź korzeń z głębokością 0.
W węźle i o głębokości d zakończ, jeśli i wykracza poza koniec lub tree[i] ma wartość -1.
Jeśli istnieje tylko d list, dodaj pustą. Dołącz tree[i] do listy d.
Odwiedź 2i+1, a następnie 2i+2, oba z głębokością d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Wszerz, jeden poziom na rundę

Intuicja

Wyjmij węzeł z kolejki i dodaj do niej jego dzieci, zaczynając od lewego. Poziom d+1 trafia do kolejki dopiero wtedy, gdy opuszcza ją poziom d, więc węzły opuszczają kolejkę poziomami, od lewej do prawej.

Aby podzielić ten strumień na poziomy, odczytaj rozmiar kolejki na początku rundy. Poprzedniego poziomu już nie ma, a żaden węzeł z następnego jeszcze nie dotarł, więc kolejka zawiera dokładnie bieżący poziom. Pobierz tyle węzłów, aby utworzyć jeden wiersz; ich dzieci poczekają na następną rundę. W przykładzie 1 rundy pobierają 1, 2, 3 i 1 węzły.

Każdy węzeł trafia do kolejki i opuszcza ją dokładnie raz: czas O(n). Kolejka mieści mniej więcej jeden poziom, maksymalnie 8,192 węzłów na najgłębszym poziomie pełnego drzewa o 14 poziomach.

Algorytm

Wstaw indeks korzenia 0 do kolejki.
Gdy kolejka nie jest pusta, odczytaj jej rozmiar s i rozpocznij pusty wiersz.
Wyjmij s indeksów. Dla każdego indeksu i dopisz tree[i] do wiersza.
Dodaj 2i+1, a następnie 2i+2 do kolejki, jeśli indeks znajduje się w tablicy i nie zawiera -1.
Dopisz wiersz do wyniku i rozpocznij następną rundę.

from collections import deque


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

Pułapki i przypadki brzegowe

Odczytywanie rozmiaru kolejki podczas jej opróżniania. W while (j < queue.length) długość rośnie, gdy pojawiają się dzieci, więc kolejny poziom przedostaje się do bieżącego wiersza.
Dodawanie prawego dziecka przed lewym albo odwiedzanie najpierw prawego poddrzewa. Wtedy drugi poziom w przykładzie 1 ma postać [2, 9].
Pominięcie sprawdzania warunku granicznego child < n. Dzieci najgłębiej położonych węzłów znajdują się poza końcem tablicy.
Usuwanie elementu z początku zwykłej listy tablicowej, co w wielu językach powoduje każdorazowe przesunięcie całej kolejki. Użyj prawdziwej kolejki albo indeksu początku.
Traktowanie -1 jako węzła. Nigdy nie trafia on do wiersza ani do kolejki: [7, -1, -1] daje [[7]], a nie [[7], []].

Najczęstsze pytania3

Jaka jest złożoność czasowa przechodzenia przez drzewo binarne poziomami?

Oba rozwiązania odwiedzają każdy węzeł raz: czas O(n) dla n węzłów. Odpowiedź zawiera n wartości, więc zajętość pamięci wynosi O(n). Poza tym kolejka przechowuje mniej więcej tyle elementów, ile jest na najszerszym poziomie, a rekurencja — tyle, ile wynosi wysokość drzewa.

Skąd wiadomo, gdzie kończy się jeden poziom w przeszukiwaniu wszerz?

Odczytaj rozmiar kolejki na początku każdej rundy i pobierz dokładnie tyle węzłów. Działają też dwa inne sposoby: przechowuj bieżący poziom i następny poziom na dwóch osobnych listach albo po każdym poziomie dodawaj do kolejki znacznik.

Tablica jest już przechowywana poziom po poziomie. Dlaczego nie odczytać jej fragmentami?

W tym formacie działa to tak: poziom d, z korzeniem na pozycji 0, wypełnia indeksy od 2^d-1 do 2^(d+1)-2, więc zbieraj niepuste wartości z każdego zakresu, aż trafisz na zakres bez żadnych wartości. Na rozmowach kwalifikacyjnych zwykle przekazuje się obiekty węzłów ze wskaźnikami, a do tego formatu można przenieść tylko kolejkę.

def levelOrder(tree):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Oczekiwany wynik

[[4], [9, 2], [6, 8, 5], [3]]