Construct Binary Tree from Preorder and Inorder Traversal

Q: Dlaczego do odtworzenia drzewa binarnego potrzebujesz zarówno przejścia preorder, jak i inorder?

Sam preorder nie określa kształtu. Przejście preorder [1, 2] pasuje do drzewa, w którym 2 jest lewym dzieckiem 1 , oraz do takiego, w którym jest jego prawym dzieckiem. Inorder rozstrzyga: [2, 1] umieszcza 2 po lewej stronie, a [1, 2] po prawej. Przy różnych wartościach ta para opisuje dokładnie jedno drzewo.

Q: Czy potrafisz odtworzyć drzewo binarne na podstawie przejścia preorder i postorder?

Nie zawsze. Przejście preorder [1, 2] i postorder [2, 1] pasują zarówno do lewego, jak i prawego dziecka, ponieważ żadne z tych przejść nie umieszcza korzenia między jego poddrzewami. Ta para wystarcza tylko w przypadku pełnego drzewa binarnego, w którym każdy węzeł ma zero albo dwoje dzieci.

ŚredniePrzechodzenie drzewa Haszowanie Rekurencja

+10

Otrzymujesz dwie tablice, preorder i inorder, zawierające różne wartości tego samego drzewa binarnego. Przejście preorder odwiedza węzeł, następnie jego lewe poddrzewo, a potem prawe poddrzewo. Przejście inorder odwiedza lewe poddrzewo, następnie węzeł, a potem prawe poddrzewo.

Odtwórz drzewo i zwróć je jako tablicę w kolejności poziomami: korzeń pod indeksem 0, dzieci elementu o indeksie i pod indeksami 2i+1 (lewe) i 2i+2 (prawe), a dla każdego pustego miejsca wartość -1. Tablica kończy się na ostatnim węźle, bez końcowych wartości -1.

Funkcja

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: wartości w porządku preorder: węzeł, lewe poddrzewo, prawe poddrzewo
inorderinteger-array: wartości w kolejności inorder: lewe poddrzewo, węzeł, prawe poddrzewo
Zwracainteger-array: drzewo w kolejności poziomami, z wartością -1 dla pustych miejsc i bez końcowych wartości -1

Ograniczenia

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, a wszystkie wartości są różne.
inorder zawiera te same wartości, a obie tablice opisują to samo drzewo binarne.
Głębokość drzewa wynosi co najwyżej 14, więc każdy indeks w odpowiedzi jest mniejszy niż 2¹⁴-1 = 16383.

Przykłady

Wejście: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Wyjście: [7, 3, 4, 0, 9, -1, 6]
Wyjaśnienie: Preorder zaczyna się od korzenia, 7. Znajduje się on na pozycji 3 w inorder, więc 0, 3, 9 trafiają w lewo, a 4, 6 w prawo. 4 ma tylko prawe dziecko, 6, więc indeks 5 pozostaje równy -1.

Wejście: preorder = [1, 2, 3]inorder = [2, 3, 1]
Wyjście: [1, 2, -1, -1, 3]
Wyjaśnienie: Korzeń 1 występuje na końcu w inorder, więc indeks 2 to -1. Spośród 2, 3 preorder wymienia najpierw 2, a inorder umieszcza 3 po nim, więc 3 jest jego prawym dzieckiem, o indeksie 4.

Pytanie dodatkowe

Czy potrafisz odbudować drzewo bez rekurencji, podczas jednego przejścia po preorder, używając jawnego stosu?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Przejście preorder podaje korzeń każdego poddrzewa: pierwszą wartość jego zakresu. Przejście inorder wyznacza podział: wartości przed korzeniem trafiają w lewo, a wartości po nim — w prawo. Rekurencja dla obu połówek odtwarza drzewo, a mapa przypisująca wartościom pozycje w przejściu inorder pozwala znaleźć każdy korzeń w jednym kroku.

Rekurencyjny podział z wyszukiwaniem korzenia

Intuicja

W porządku preorder lewe poddrzewo występuje po swoim korzeniu i zajmuje po jednym wpisie na każdą wartość — jest ich m-lo, gdzie m to pozycja korzenia w porządku inorder. Prawe poddrzewo występuje po nim, więc jego korzeń znajduje się pod indeksem pre+1+(m-lo). W pierwszym przykładzie lewa część 0, 3, 9 zawiera trzy wartości, więc prawe poddrzewo zaczyna się pod indeksem preorder 4, czyli od wartości 4.

Głębokość nie większa niż 14 sprawia, że każdy indeks wyjściowy jest mniejszy niż 2^14-1. Wypełnij tyle komórek wartością -1, zapisz każdą wartość pod jej indeksem, a na końcu usuń końcowe wpisy -1.

Przeszukiwanie każdego zakresu inorder w celu znalezienia jego korzenia ma koszt O(n·h): zakresy na tym samym poziomie nie nakładają się, więc jeden poziom przeszukuje najwyżej n wpisów, czyli w tym przypadku najwyżej 14 × 3000 = 42000 kroków. Bez ograniczenia głębokości drzewo w kształcie ścieżki sprawia, że koszt wynosi O(n²).

Algorytm

Utwórz out z 2^14-1 elementami, wszystkie równe -1.
Napisz build(pre, lo, hi, h): jeśli lo > hi, zakończ. W przeciwnym razie zapisz preorder[pre] w out[h].
Przeszukaj inorder od lo, aby znaleźć pozycję korzenia m. Lewe poddrzewo ma m-lo wartości.
Wywołaj build(pre+1, lo, m-1, 2*h+1) oraz build(pre+1+(m-lo), m+1, hi, 2*h+2).
Wywołaj build(0, 0, n-1, 0), a następnie usuń końcowe elementy -1 i zwróć pozostałe.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Podziel rekurencyjnie za pomocą mapy pozycji

Intuicja

Wartości są różne, więc każda ma dokładnie jedną pozycję w inorder. Zapisz ją w mapie przyporządkowującej wartość do pozycji przed rozpoczęciem rekurencji, a każde wyszukiwanie korzenia zajmie jeden krok.

Utworzenie mapy zajmuje O(n), a każda wartość jest następnie umieszczana raz przy stałym nakładzie pracy, więc łączny czas wynosi O(n). Mapa zajmuje O(n) miejsca, a rekurencja wykorzystuje jedną ramkę na każdym poziomie. W C i R wartości wynoszą co najwyżej 10^4, więc zwykła tablica z 10^4+1 elementami może służyć jako mapa.

Algorytm

Utwórz mapę przypisującą każdej wartości z inorder jej pozycję.
Utwórz out z 2^14-1 elementami, z których każdy ma wartość -1.
W funkcji build(pre, lo, hi, h) zakończ działanie, jeśli lo > hi; w przeciwnym razie zapisz preorder[pre] w out[h] i wyszukaj jego pozycję m na mapie.
Wywołaj rekurencyjnie build(pre+1, lo, m-1, 2*h+1) oraz build(pre+1+(m-lo), m+1, hi, 2*h+2).
Wywołaj build(0, 0, n-1, 0), a następnie usuń końcowe elementy -1 i zwróć pozostałe.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Pułapki i przypadki brzegowe

Rozpoczynanie prawego poddrzewa od pre+1+m zamiast pre+1+(m-lo). Działa, gdy lo wynosi 0, jak przy wywołaniu na najwyższym poziomie, ale zawodzi, gdy zakres zaczyna się później.
Pomijanie luk. Brakujący potomek nadal zajmuje swoje miejsce, więc wynik drugiego przykładu to [1, 2, -1, -1, 3], a nie [1, 2, 3].
Pozostawianie końcowych wpisów -1. Zwrócenie wszystkich 2^14-1 komórek daje w pierwszym przykładzie 16376 dodatkowych wpisów -1.
Kopiowanie fragmentów obu tablic przy każdym wywołaniu, co dodaje O(n) na poziom. Przekazuj zakresy indeksów.
W Lua i R tablice zaczynają się od indeksu 1. Do obliczeń używaj pozycji indeksowanych od 0, a odczytuj preorder[pre + 1] i out[h + 1].

Najczęstsze pytania3

Dlaczego do odtworzenia drzewa binarnego potrzebujesz zarówno przejścia preorder, jak i inorder?

Sam preorder nie określa kształtu. Przejście preorder [1, 2] pasuje do drzewa, w którym 2 jest lewym dzieckiem 1, oraz do takiego, w którym jest jego prawym dzieckiem. Inorder rozstrzyga: [2, 1] umieszcza 2 po lewej stronie, a [1, 2] po prawej. Przy różnych wartościach ta para opisuje dokładnie jedno drzewo.

Jaka jest złożoność czasowa budowania drzewa binarnego na podstawie przejścia preorder i inorder?

Z mapą przyporządkowującą wartość do pozycji w porządku inorder złożoność czasowa wynosi O(n), a dodatkowa złożoność pamięciowa O(n). Bez mapy wyszukiwanie korzenia w każdym zakresie inorder kosztuje O(n·h), co w przypadku drzewa o kształcie ścieżki daje O(n²).

Czy potrafisz odtworzyć drzewo binarne na podstawie przejścia preorder i postorder?

Nie zawsze. Przejście preorder [1, 2] i postorder [2, 1] pasują zarówno do lewego, jak i prawego dziecka, ponieważ żadne z tych przejść nie umieszcza korzenia między jego poddrzewami. Ta para wystarcza tylko w przypadku pełnego drzewa binarnego, w którym każdy węzeł ma zero albo dwoje dzieci.

def buildTree(preorder, inorder):
    # Wpisz kod tutaj

Test #1

Test #2

Argumenty

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Oczekiwany wynik

[7, 3, 4, 0, 9, -1, 6]