Binary Tree Level Order Traversal

Q: Jaka jest złożoność czasowa przechodzenia przez poziomy drzewa binarnego?

Zarówno rozwiązanie wszerz, jak i w głąb odwiedza każdy węzeł raz, więc działa w czasie O(n) dla n węzłów. Odpowiedź zawiera n wartości, więc zajmuje O(n) pamięci. Ponadto kolejka przechowuje co najwyżej mniej więcej tyle elementów, ile jest na najszerszym poziomie, a rekurencja — co najwyżej 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. W tym momencie kolejka zawiera dokładnie węzły jednego poziomu, więc pobranie tej liczby węzłów pobiera cały poziom i nic więcej. Działają też dwa inne sposoby: przechowuj bieżący poziom i następny poziom na dwóch oddzielnych listach albo umieszczaj znacznik po każdym poziomie.

Q: Czy można wykonać przejście poziomami za pomocą przeszukiwania w głąb?

Tak. Przekaż każdemu węzłowi jego głębokość i dodaj jego wartość do listy dla tej głębokości. Dopóki przejście odwiedza lewe poddrzewo przed prawym, każda lista będzie uporządkowana od lewej do prawej. To również O(n) ; przeszukiwanie wszerz pasuje tu bardziej bezpośrednio, ponieważ tworzy poziomy we właściwej kolejności.

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

W tym formacie sprawdza się następujące podejście: poziom d zajmuje indeksy od 2^d-1 do 2^(d+1)-2 , więc możesz zebrać niepuste wartości z każdego zakresu i zatrzymać się na pierwszym zakresie, w którym nie ma żadnych wartości. Na rozmowie kwalifikacyjnej drzewo zwykle jest jednak reprezentowane przez obiekty węzłów ze wskaźnikami do lewego i prawego dziecka, bez indeksów, które można by wykorzystać do wyodrębniania fragmentów. Przechodzenie oparte na kolejce można zastosować również w tej postaci oraz w wariantach, takich jak porządek zygzakowaty czy widok drzewa z prawej strony.

ŚredniePrzechodzenie drzewa Kolejka

+10

Otrzymujesz drzewo binarne zapisane w tablicy tree. 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), -1 oznacza puste miejsce, a tablica może kończyć się dodatkowymi wpisami -1.

Zwróć wartości węzłów poziomami: listę zawierającą wartość korzenia, następnie listę z wartościami poziom niżej, od lewej do prawej, i tak dalej aż do najgłębszego poziomu.

Funkcja

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

treeinteger-array: drzewo w kolejności kopcowej, z wartością -1 w pustym miejscu
Zwracainteger-2d-array: jedna lista wartości na poziom, najpierw poziom najwyższy, każda od lewej do prawej

Ograniczenia

1 ≤ tree.length ≤ 32767
Każdy element tree[i] ma wartość -1 lub wartość spełniającą 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 zawierać dodatkowe wpisy -1 po ostatnim węźle.
Oboje dzieci pustego miejsca również są puste, a głębokość wynosi 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: Korzeń 4 ma dzieci 9 i 2 na indeksach 1 i 2. Indeks 3 jest pusty, więc na trzecim poziomie znajduje się 6 (indeks 4, pod 9), a następnie 8 i 5 (indeksy 5 i 6, pod 2). 3 na indeksie 9 jest lewym dzieckiem 6 i znajduje się samotnie na czwartym poziomie.

Wejście: tree = [7, -1, -1]
Wyjście: [[7]]
Wyjaśnienie: Oboje dzieci korzenia mają wartość -1, więc drzewo składa się z jednego 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 o indeksie 1 i 5 o indeksie 3. Na każdym poziomie znajduje się jedna wartość, a końcowe wpisy -1 niczego nie dodają.

+15 ukrytych testów przy wysłaniu

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 zostać wypisany jako osobna lista, uporządkowana od lewej do prawej. Wyszukiwanie wszerz z użyciem kolejki odwiedza węzły dokładnie w tej kolejności. Trzeba jeszcze wiedzieć, gdzie kończy się poziom: na początku każdej rundy kolejka zawiera cały bieżący poziom i nic więcej, więc jej rozmiar mówi, ile węzłów należy pobrać. Sprawdza się również przejście w głąb, o ile zachowuje głębokość każdego węzła i przechodzi najpierw w lewo, a potem w prawo.

Wgłąb, uporządkowane według głębokości

Intuicja

Najpierw poruszanie się po tablicy. Lewe dziecko węzła o indeksie i znajduje się pod indeksem 2i+1, a prawe pod indeksem 2i+2. Dziecko nie istnieje, gdy jego indeks wykracza poza koniec tablicy lub zawiera -1. W przykładzie 1 dzieci węzła 9 (indeks 1) znajdują się pod indeksami 3 i 4, które zawierają -1 i 6, więc 9 ma tylko prawe dziecko.

Teraz przejdź przez drzewo w głąb, przekazując każdemu węzłowi jego głębokość, przy czym korzeń ma głębokość 0. Prowadź jedną listę dla każdej głębokości. Gdy dotrzesz do węzła na głębokości d, dopisz jego wartość do listy d; jeśli dotychczas istnieje tylko d list, oznacza to, że jest to pierwszy węzeł na nowym poziomie, więc najpierw utwórz nową listę.

Dlaczego węzły na każdym poziomie pojawiają się od lewej do prawej? Przejście kończy odwiedzanie całego lewego poddrzewa węzła, zanim przejdzie do jego prawego poddrzewa. Weźmy dwa węzły na tym samym poziomie: w miejscu, w którym ich ścieżki od korzenia się rozchodzą, jedna prowadzi w lewo, a druga w prawo, i przejście najpierw dociera do lewego węzła. W przykładzie 1 kolejność to 4, 9, 6, 3, 2, 8, 5, co wypełnia listy jako [4], [9, 2], [6, 8, 5], [3].

Każdy węzeł jest odwiedzany raz, więc czas działania wynosi O(n) dla n węzłów, a listy zawierają łącznie n wartości. Rekurencja sięga tylko tak głęboko jak samo drzewo, tutaj najwyżej 15 poziomów. Wersja w R używa zamiast tego jawnego stosu, odkładając prawe dziecko przed lewym, aby lewe zostało zdjęte jako pierwsze, a następnie grupuje wartości według głębokości za pomocą split.

Algorytm

Utwórz pustą listę poziomów.
Odwiedź korzeń z głębokością 0.
W węźle i o głębokości d zatrzymaj się, 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

Kolejka zwraca wartości w takiej kolejności, w jakiej zostały do niej wstawione. Wstaw korzeń. Następnie wielokrotnie wyjmuj węzeł i wstawiaj jego dzieci, najpierw lewe dziecko. Każdy węzeł poziomu d+1 trafia do kolejki, gdy opuszcza ją jego rodzic z poziomu d, więc wszystkie węzły poziomu d opuszczają kolejkę, zanim zrobi to jakikolwiek węzeł poziomu d+1, a w obrębie jednego poziomu węzły opuszczają ją od lewej do prawej.

W ten sposób otrzymujemy jeden ciąg wartości w kolejności poziomami. Aby podzielić go na poziomy, odczytaj rozmiar kolejki na początku rundy. W tym momencie kolejka zawiera dokładnie bieżący poziom: poprzedni poziom został już przetworzony, a żaden węzeł z następnego poziomu jeszcze do niej nie trafił. Wyjmij tyle węzłów i umieść je na jednej liście. Dodane przez nie dzieci należą do następnej rundy.

W przykładzie 1 kolejka początkowo zawiera [4]: wyjmij 1 węzeł, wiersz [4], a do kolejki trafiają 9, 2. Wyjmij 2 węzły, wiersz [9, 2], a do kolejki trafiają 6, 8, 5. Wyjmij 3 węzły, wiersz [6, 8, 5], a do kolejki trafia 3. Wyjmij 1 węzeł, wiersz [3], a kolejka jest pusta.

Każdy węzeł trafia do kolejki i ją opuszcza dokładnie raz, więc złożoność czasowa wynosi O(n). Kolejka zawiera najwyżej mniej więcej tyle węzłów, ile jest na jednym poziomie — do 16384 węzłów na najgłębszym poziomie pełnego drzewa o głębokości 14. Użyj prawdziwej kolejki albo indeksu początku: wyjmowanie pierwszego elementu ze zwykłej listy tablicowej przesuwa każdy kolejny element w wielu językach.

Algorytm

Umieść indeks korzenia 0 w kolejce.
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.
Dodaj wiersz do odpowiedzi i rozpocznij kolejną 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

Samo przechodzenie po drzewie jest krótkie. Błędy dotyczą granic poziomów i pustych miejsc.

Odczytywanie rozmiaru kolejki, gdy nadal ją opróżniasz. W pętli takiej jak while (j < queue.length) długość rośnie, gdy dodawane są dzieci, więc następny poziom trafia do bieżącego wiersza. Odczytaj rozmiar raz, przed rozpoczęciem rundy.
Dodawanie prawego dziecka przed lewym. Każdy poziom będzie wtedy zwracany od prawej do lewej. To samo dotyczy przejścia w głąb, które najpierw odwiedza prawe poddrzewo.
Traktowanie -1 jako wartości. Puste miejsce nie jest węzłem, więc nigdy nie trafia do wiersza ani do kolejki.
Zapominanie o sprawdzeniu granic. Dzieci najgłębszych węzłów mogą znajdować się poza końcem tablicy, więc sprawdź child < n, zanim odczytasz tree[child].
Zwracanie pustych poziomów. Końcowe wpisy -1 nie zawierają żadnych węzłów, więc odpowiedzią dla [7, -1, -1] jest [[7]], a nie [[7], []].

Najczęstsze pytania4

Jaka jest złożoność czasowa przechodzenia przez poziomy drzewa binarnego?

Zarówno rozwiązanie wszerz, jak i w głąb odwiedza każdy węzeł raz, więc działa w czasie O(n) dla n węzłów. Odpowiedź zawiera n wartości, więc zajmuje O(n) pamięci. Ponadto kolejka przechowuje co najwyżej mniej więcej tyle elementów, ile jest na najszerszym poziomie, a rekurencja — co najwyżej 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. W tym momencie kolejka zawiera dokładnie węzły jednego poziomu, więc pobranie tej liczby węzłów pobiera cały poziom i nic więcej. Działają też dwa inne sposoby: przechowuj bieżący poziom i następny poziom na dwóch oddzielnych listach albo umieszczaj znacznik po każdym poziomie.

Czy można wykonać przejście poziomami za pomocą przeszukiwania w głąb?

Tak. Przekaż każdemu węzłowi jego głębokość i dodaj jego wartość do listy dla tej głębokości. Dopóki przejście odwiedza lewe poddrzewo przed prawym, każda lista będzie uporządkowana od lewej do prawej. To również O(n); przeszukiwanie wszerz pasuje tu bardziej bezpośrednio, ponieważ tworzy poziomy we właściwej kolejności.

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

W tym formacie sprawdza się następujące podejście: poziom d zajmuje indeksy od 2^d-1 do 2^(d+1)-2, więc możesz zebrać niepuste wartości z każdego zakresu i zatrzymać się na pierwszym zakresie, w którym nie ma żadnych wartości. Na rozmowie kwalifikacyjnej drzewo zwykle jest jednak reprezentowane przez obiekty węzłów ze wskaźnikami do lewego i prawego dziecka, bez indeksów, które można by wykorzystać do wyodrębniania fragmentów. Przechodzenie oparte na kolejce można zastosować również w tej postaci oraz w wariantach, takich jak porządek zygzakowaty czy widok drzewa z prawej strony.

Python

def levelOrder(tree):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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