Binary Tree Zigzag Level Order Traversal

+10

Otrzymujesz drzewo binarne zapisane w tablicy root. 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 poziom po poziomie w kolejności zygzakowatej: poziom korzenia od lewej do prawej, następny od prawej do lewej i tak dalej, naprzemiennie aż do najgłębszego poziomu. Nazywa się to również spiralnym przejściem poziomami.

Funkcja

zigzagLevelOrder(root: integer-array) → integer-2d-array

rootinteger-array: drzewo w porządku kopcowym, z wartością -1 w pustym miejscu
Zwracainteger-2d-array: jedna lista wartości na poziom, najpierw najwyższy poziom, naprzemiennie od lewej do prawej i od prawej do lewej

Ograniczenia

1 ≤ root.length ≤ 32767
Każdy element root[i] ma wartość -1 lub wartość spełniającą warunek 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.
Oboje dzieci pustego miejsca również są puste, a drzewo ma co najwyżej 14 poziomów.

Przykłady

Wejście: root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Wyjście: [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
Wyjaśnienie: Czytane od lewej do prawej, poziomy to 8; 12, 5; 1, 9, 14; 4, 2, 11. Poziomy 1 i 3 są odczytywane od końca: [5, 12] i [11, 2, 4].

Wejście: root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
Wyjście: [[1], [3, 2], [4, 5, 6, 7]]
Wyjaśnienie: Pełne drzewo o trzech poziomach: środkowy poziom jest odwrócony do [3, 2], a trzeci biegnie ponownie od lewej do prawej. Dwa końcowe wpisy -1 oznaczają puste miejsca na dzieci węzła 4.

Pytanie dodatkowe

Czy możesz umieścić każdą wartość od razu na jej końcowym miejscu w wierszu, bez odwracania i bez drugiego stosu?

Rozwiązanie

Poziomy pochodzą ze zwykłego przeszukiwania wszerz. Nowym elementem jest kierunek: co drugi poziom jest odwrócony. Możesz odwrócić nieparzyste wiersze po ich utworzeniu albo przechowywać każdy poziom na stosie, który zwraca elementy w kolejności przeciwnej do kolejności ich dodawania.

Kolejność poziomów, a następnie odwróć co drugi poziom

Intuicja

Kolejka przetwarzająca jeden poziom na rundę zwraca wartości każdego poziomu od lewej do prawej. Ponumeruj poziomy od 0, zaczynając od korzenia: porządek zygzakowaty odczytuje nieparzyste poziomy od prawej do lewej, więc odwrócenie dokładnie tych wierszy daje odpowiedź.

Wyszukiwanie odwiedza każdy węzeł raz, a każde odwrócenie dotyka każdej wartości jeszcze raz, więc złożoność czasowa wynosi O(n).

Algorytm

Rozpocznij kolejkę z indeksem 0.
W każdej rundzie zapisz długość kolejki s, zdejmij z kolejki s indeksów i umieść je w nowym wierszu, a następnie dodaj do kolejki istniejące dzieci każdego z nich, najpierw lewe, potem prawe.
Jeśli odpowiedź zawiera już nieparzystą liczbę wierszy, odwróć wiersz.
Dodaj wiersz i kontynuuj, aż kolejka będzie pusta.

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    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(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

Dwa stosy

Intuicja

Przechowuj bieżący poziom na stosie, z którego elementy są zdejmowane w kierunku odczytywania poziomu, i umieszczaj dzieci każdego zdjętego węzła na drugim stosie. Gdy bieżący stos się opróżni, drugi będzie zawierał następny poziom.

Kolejność umieszczania elementów na stosie sprawia, że to działa. Zdejmując elementy od lewej do prawej, umieszczaj lewe dziecko każdego węzła, a następnie prawe: prawe dziecko węzła położonego najbardziej na prawo trafia na stos jako ostatnie, więc następny poziom jest zdejmowany od jego prawego końca. Zdejmując elementy od prawej do lewej, umieszczaj najpierw prawe dziecko, a potem lewe; lewe dziecko węzła położonego najbardziej na lewo trafia na stos jako ostatnie.

Przykład 1: zdejmij 8, umieść na stosie 12, 5. Zdejmij 5, 12, a następnie umieść na stosie 14 z węzła 5 oraz 9, 1 z węzła 12. Zdejmij 1, 9, 14, a następnie umieść na stosie 4, 2 z węzła 9 oraz 11 z węzła 14. Zdejmij 11, 2, 4.

Każdy węzeł jest umieszczany na stosie i zdejmowany z niego raz: czas O(n), bez etapu odwracania.

Algorytm

Umieść indeks korzenia 0 na stosie i zacznij czytać od lewej do prawej.
Gdy stos nie jest pusty, zdejmij z niego każdy indeks i umieść go w nowym wierszu, a istniejące dzieci każdego zdjętego węzła umieść na drugim stosie: najpierw lewe, potem prawe, gdy czytasz od lewej do prawej; w przeciwnym razie najpierw prawe, potem lewe.
Dołącz wiersz do odpowiedzi.
Ustaw drugi stos jako bieżący, zmień kierunek i powtórz.

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels

Pułapki i przypadki brzegowe

Odwracanie kolejności, w jakiej dzieci trafiają do pojedynczej kolejki. Rodzeństwo zamienia się miejscami, ale rodzice zachowują swoją kolejność: trzeci poziom przykładu 1 daje wynik [9, 1, 14].
Liczenie poziomów od 1. Każde odwrócenie przesuwa wynik o jeden poziom, a przykład 1 daje [[8], [12, 5], [14, 9, 1], [4, 2, 11]].
Używanie tej samej kolejności umieszczania na stosie na każdym poziomie w wersji z dwoma stosami. Trzeci poziom przykładu 1 zostaje wtedy zdjęty ze stosu jako [9, 1, 14].
Umieszczanie dzieci na stosie, z którego nadal zdejmujesz elementy. Dzieci zostają zdjęte, zanim pojawi się reszta poziomu ich rodzica.
Sortowanie wiersza zamiast odwracania jego kolejności. Ostatni poziom przykładu 1 musi mieć postać [11, 2, 4], której nie daje żadne sortowanie.

Najczęstsze pytania3

Jaka jest różnica między przechodzeniem w kolejności zygzakowatej a przechodzeniem poziomami?

Odwiedzają te same poziomy z tymi samymi węzłami. Przejście poziomami odczytuje każdy poziom od lewej do prawej; przejście zygzakiem odczytuje co drugi poziom od prawej do lewej, zaczynając od poziomu poniżej korzenia. Oba działają w czasie O(n).

Czy przechodzenie zygzakiem jest tym samym co przechodzenie po drzewie w porządku spiralnym?

Tak, obie nazwy opisują ten sam sposób przechodzenia. Niektóre teksty rozpoczynają drugi poziom od lewej zamiast od prawej, co jedynie przesuwa odbicia o jeden poziom. Tutaj poziom korzenia przebiega od lewej do prawej, a następny od prawej do lewej.

Czy można wykonać przejście poziomami zygzakiem za pomocą dwustronnej kolejki?

Tak. Zachowuj kolejność od lewej do prawej dla każdego poziomu w kolejce dwustronnej. Na poziomie przetwarzanym od lewej do prawej pobieraj węzły z przodu i dodawaj ich dzieci, najpierw lewe, a potem prawe, z tyłu. Na poziomie przetwarzanym od prawej do lewej pobieraj węzły z tyłu i dodawaj ich dzieci, najpierw prawe, a potem lewe, z przodu. Liczba elementów pobieranych na początku rundy nadal wyznacza poziom.

def zigzagLevelOrder(root):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argument

root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]

Oczekiwany wynik

[[8], [5, 12], [1, 9, 14], [11, 2, 4]]