Boundary Traversal of Binary Tree

Q: Jaka jest złożoność czasowa przechodzenia po granicy?

O(n) . Dwa przejścia po krawędziach podążają każdorazowo jedną ścieżką, a przejście po liściach odwiedza każdy węzeł jeden raz. Dodatkowa przestrzeń wynosi O(h) dla rekurencji lub stosu.

ŚredniePrzechodzenie drzewa

+10

Tablica root przechowuje drzewo binarne w porządku poziomami: korzeń znajduje się pod indeksem 0, dzieci węzła o indeksie i pod indeksami 2i+1 (lewe) i 2i+2 (prawe), -1 oznacza puste miejsce, a na końcu mogą znajdować się dodatkowe wpisy -1. Liść to węzeł bez dzieci.

Zwróć granicę w kierunku przeciwnym do ruchu wskazówek zegara, zaczynając od korzenia:

Korzeń.
Lewa granica, od góry do dołu: zaczynając od lewego dziecka korzenia, przechodź do lewego dziecka, jeśli istnieje, a w przeciwnym razie do prawego dziecka. Zatrzymaj się przed liściem.
Każdy liść, od lewej do prawej.
Prawa granica, od dołu do góry: lustrzane odbicie lewej granicy, zaczynając od prawego dziecka korzenia.

Żaden węzeł nie jest wypisywany dwukrotnie, więc drzewo z jednym węzłem zwraca tylko korzeń.

Funkcja

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

rootinteger-array: drzewo binarne w kolejności poziomami, z wartością -1 oznaczającą puste miejsce
Zwracainteger-array: wartości graniczne, przeciwnie do ruchu wskazówek zegara od korzenia

Ograniczenia

1 ≤ root.length ≤ 32767
Każde root[i] jest równe -1 lub ma wartość z zakresu 0 ≤ root[i] ≤ 10⁵.
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 głębokość wynosi najwyżej 14.
Wartości węzłów są różne.

Przykłady

Wejście: root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Wyjście: [7, 3, 1, 4, 6, 8, 9]
Wyjaśnienie: Po korzeniu 7 lewą granicą jest 3: jego potomek 1 jest liściem. Liście to 1, 4, 6, 8. Prawą granicą jest 9, nad liściem 8.

Wejście: root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
Wyjście: [10, 4, 6, 5, 8]
Wyjaśnienie: 4 nie ma lewego dziecka, więc lewa granica przechodzi do 6, a następnie zatrzymuje się na liściu 5. Dalej są liście 5, 8. Korzeń nie ma prawego dziecka.

Pytanie dodatkowe

Jak wypisać granicę zgodnie z ruchem wskazówek zegara: korzeń, prawą krawędź od góry do dołu, liście od prawej do lewej, a następnie lewą krawędź od dołu do góry?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Odpowiedź łączy cztery części: korzeń, ścieżkę w dół lewą krawędzią, liście od lewej do prawej oraz ścieżkę w dół prawą krawędzią, odczytywaną od tyłu. W miejscach połączeń liść kończący krawędź oraz korzeń będący liściem należy wymienić tylko raz.

Przejdź osobno przez trzy części

Intuicja

Każda krawędź odpowiada jednej ścieżce: od dziecka korzenia wypisuj węzły, aż następny byłby liściem — ten liść wypisuje zamiast tego część dotycząca liści. Przejście w porządku preorder, najpierw w lewo, a potem w prawo, odwiedza liście od lewej do prawej, ponieważ każdy węzeł lewego poddrzewa znajduje się na lewo od prawego poddrzewa, niezależnie od jego głębokości. Zbierz prawą krawędź od góry do dołu i dołącz ją w odwrotnej kolejności.

Każda krawędź przebiega wzdłuż jednej ścieżki, a przejście po liściach odwiedza każdy węzeł raz: czas O(n), rekurencja ma głębokość h poziomów.

Algorytm

Zacznij od korzenia; jeśli jest liściem, zwróć go.
Z indeksu 1, dopóki węzeł istnieje i nie jest liściem, dodaj go i przejdź do jego lewego dziecka albo do prawego, jeśli nie ma lewego.
Przejdź w porządku preorder, najpierw w lewo, od indeksów 1 i 2, dodając każdy liść.
Z indeksu 2 wykonaj to samo co w kroku 2, wybierając prawe dzieci, i zbierając węzły.
Dodaj zebrane węzły w odwrotnej kolejności.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    def is_leaf(i):
        return not real(2 * i + 1) and not real(2 * i + 2)

    result = [root[0]]
    if is_leaf(0):
        return result

    # 1. The left boundary, top-down, stopping before its leaf.
    i = 1
    while real(i) and not is_leaf(i):
        result.append(root[i])
        i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2

    # 2. Every leaf: a pre-order walk meets them from left to right.
    def add_leaves(i):
        if not real(i):
            return
        if is_leaf(i):
            result.append(root[i])
            return
        add_leaves(2 * i + 1)
        add_leaves(2 * i + 2)

    add_leaves(1)
    add_leaves(2)

    # 3. The right boundary, collected top-down and added bottom-up.
    right = []
    i = 2
    while real(i) and not is_leaf(i):
        right.append(root[i])
        i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
    result.extend(reversed(right))
    return result

Jedno przejście wstępne z flagami krawędzi

Intuicja

Połącz przejścia w jedno przejście w porządku pre-order, używając stosu i przypisując każdemu węzłowi flagę: 1 na lewej krawędzi, 2 na prawej krawędzi, 0 wewnątrz. Dzieci korzenia zaczynają z flagami 1 i 2. Węzeł krawędziowy przekazuje swoją flagę dziecku po swojej stronie lub jedynemu dziecku; każde inne dziecko otrzymuje 0. W drugim przykładzie 1 przechodzi z 4 do 6, a następnie do 5.

Gdy węzły schodzą ze stosu, dodawaj każdy liść i każdy węzeł niebędący liściem oznaczony flagą 1; zbieraj węzły niebędące liśćmi oznaczone flagą 2 i dodaj je na końcu w odwrotnej kolejności. Przejście w porządku pre-order dociera do każdego węzła lewej krawędzi przed jakimkolwiek liściem, ponieważ krawędź skręca w prawo tylko tam, gdzie nic nie leży po jej lewej stronie.

Algorytm

Zacznij od korzenia. Umieść jego prawe dziecko na stosie z flagą 2, a następnie lewe dziecko z flagą 1.
Zdejmij węzeł ze stosu. Dopisz go, jeśli jest liściem lub ma flagę 1; węzeł niebędący liściem z flagą 2 dodaj do prawej listy.
Umieść jego prawe dziecko na stosie, a następnie lewe dziecko, każdemu przypisując flagę określoną przez regułę.
Gdy stos będzie pusty, dopisz odwróconą prawą listę.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    result = [root[0]]
    right = []  # the right boundary, top-down; it goes on the end reversed
    # Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
    stack = []
    if real(2):
        stack.append((2, 2))
    if real(1):
        stack.append((1, 1))
    while stack:
        i, edge = stack.pop()
        has_left, has_right = real(2 * i + 1), real(2 * i + 2)
        if not has_left and not has_right:
            result.append(root[i])  # a leaf; pre-order meets them left to right
        elif edge == 1:
            result.append(root[i])  # the left boundary, top-down
        elif edge == 2:
            right.append(root[i])
        # An edge passes to the child on its own side, or to an only child.
        # The right child goes on the stack first, so the left one comes out first.
        if has_right:
            stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
        if has_left:
            stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
    result.extend(reversed(right))
    return result

Pułapki i przypadki brzegowe

Wypisywanie węzła dwa razy. Przejście po krawędziach, które nie zatrzymuje się przed liściem, wypisuje 1 dwa razy w przykładzie 1, a w drzewie składającym się z jednego węzła nie wolno ponownie wypisywać korzenia jako liścia.
Uznawanie pierwszego węzła na każdym poziomie za lewą granicę. Jeśli lewe dziecko korzenia jest liściem, a prawe poddrzewo jest głębsze, głębsze poziomy zaczynają się od węzłów prawego poddrzewa, mimo że lewa granica jest pusta.
Podążanie wyłącznie za lewymi dziećmi. W przykładzie 2 granica musi przejść od 4 do jego prawego dziecka 6.
Zbieranie liści poziom po poziomie. W przykładzie 1 otrzymujemy wtedy 1, 8, 4, 6.
W Lua i R indeksy węzłów powinny pozostać 0-indeksowane dla działania 2i+1, a odczyt powinien odbywać się za pomocą root[i + 1].

Najczęstsze pytania3

Czym jest przechodzenie po granicy drzewa binarnego?

Wypisuje obrys drzewa w kierunku przeciwnym do ruchu wskazówek zegara: korzeń, lewą krawędź od góry do dołu, liście od lewej do prawej oraz prawą krawędź od dołu do góry. Krawędzie pomijają liście, więc żaden węzeł nie pojawia się dwa razy.

Jaka jest złożoność czasowa przechodzenia po granicy?

O(n). Dwa przejścia po krawędziach podążają każdorazowo jedną ścieżką, a przejście po liściach odwiedza każdy węzeł jeden raz. Dodatkowa przestrzeń wynosi O(h) dla rekurencji lub stosu.

Czy lewa granica zawsze podąża za lewymi dziećmi?

Nie. Przechodzi do lewego dziecka, jeśli takie istnieje, a w przeciwnym razie do prawego dziecka: najbardziej zewnętrznej ścieżki widocznej z lewej strony. Jeśli korzeń nie ma lewego dziecka, lewa granica jest pusta.

def boundaryTraversal(root):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]

Oczekiwany wynik

[7, 3, 1, 4, 6, 8, 9]