Invert Binary Tree

+10

Otrzymujesz drzewo binarne zapisane w tablicy tree w kolejności poziomami. 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.

Odwróć drzewo: zamień lewe i prawe dziecko każdego węzła, tak aby całe drzewo stało się swoim lustrzanym odbiciem. Zwróć odwrócone drzewo w tej samej postaci, bez wpisów -1 na końcu.

Funkcja

invertTree(tree: integer-array) → integer-array

treeinteger-array: drzewo binarne w kolejności poziomami, z -1 oznaczającym puste miejsce
Zwracainteger-array: lustrzane odbicie drzewa w kolejności poziomami, bez końcowych wpisów -1

Ograniczenia

1 ≤ tree.length ≤ 16383
Każde 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 kończyć się dodatkowymi wpisami -1 za ostatnim węzłem.
Oba dzieci pustej pozycji również są puste, a głębokość wynosi najwyżej 14.

Przykłady

Wejście: tree = [5, 3, 8, 1, 4, -1, 9]
Wyjście: [5, 8, 3, 9, -1, 4, 1]
Wyjaśnienie: Dzieci korzenia 3 i 8 zamieniają się miejscami. Pod nimi 1 i 4, które znajdowały się poniżej 3, wracają jako 4 i 1, a 8, które miało tylko prawe dziecko 9, ma je teraz po lewej stronie.

Wejście: tree = [2, 7, -1, 6]
Wyjście: [2, -1, 7, -1, -1, -1, 6]
Wyjaśnienie: Łańcuch 2, 7, 6 przechyla się w lewo, a jego lustrzane odbicie w prawo. 7 przesuwa się z indeksu 1 na indeks 2, a 6 z indeksu 3 na indeks 6, więc odpowiedź jest dłuższa niż dane wejściowe, a w każdym pustym miejscu przed ostatnim węzłem znajduje się -1.

Wejście: tree = [1, -1, -1]
Wyjście: [1]
Wyjaśnienie: Pojedynczy węzeł jest swoim własnym odbiciem lustrzanym. Dwa wpisy -1 to dopełnienie, a w odpowiedzi pomija się każde -1 na końcu.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak sprawdzić, czy drzewo jest swoim własnym odbiciem lustrzanym, używając tych samych par indeksów, ale bez tworzenia odwróconej kopii?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Odbicie lustrzane drzewa oznacza zamianę lewego i prawego poddrzewa każdego węzła — aż do samego dołu. W przypadku obiektów węzłów oznacza to jedną zamianę na węzeł. W tej reprezentacji tablicowej miejsce węzła określa jego indeks, więc zamiana dwóch poddrzew oznacza przeniesienie wszystkich węzłów, które się w nich znajdują. Sposobem na to jest zbudowanie wyniku w nowej tablicy i skopiowanie każdego węzła bezpośrednio pod jego lustrzany indeks, przenosząc podczas przechodzenia pary indeksów: gdzie węzeł znajduje się teraz i dokąd ma trafić.

Rekurencja umieszczająca każdy węzeł na jego lustrzanym indeksie

Intuicja

Najpierw: jak poruszać się po tablicy. Węzeł o indeksie i ma lewe dziecko pod indeksem 2*i+1, a prawe dziecko pod indeksem 2*i+2. Dziecko istnieje tylko wtedy, gdy jego indeks mieści się w tablicy, a wartość w tym miejscu nie jest równa -1. W [5, 3, 8, 1, 4, -1, 9] korzeń 5 ma dzieci 3 i 8 pod indeksami 1 i 2, a węzeł 8 pod indeksem 2 ma puste lewe miejsce pod indeksem 5 i węzeł 9 pod indeksem 6.

Teraz odbicie lustrzane. Korzeń pozostaje pod indeksem 0. Lewe poddrzewo węzła staje się prawym poddrzewem jego lustrzanego odpowiednika, a prawe poddrzewo — lewym. Jeśli więc węzeł pod indeksem src trafia pod indeks dst w wyniku, jego lewe dziecko trafia pod indeks 2*dst+2, a prawe pod 2*dst+1. Zapisz place(src, dst): skopiuj wartość, a następnie wywołaj place(2*src+1, 2*dst+2) oraz place(2*src+2, 2*dst+1). Pusta pozycja kończy działanie od razu. W pierwszym przykładzie węzeł 3 pod indeksem 1 trafia pod indeks 2, więc jego lewe dziecko 1 trafia pod indeks 6, a prawe dziecko 4 pod indeks 5.

Węzeł nigdy nie zmienia poziomu, więc jego lustrzany indeks pozostaje na tym samym poziomie co poprzedni. Zaokrąglij długość w górę do pełnych poziomów (1, 3, 7, 15, ...), wypełnij tyle miejsc wartością -1, a na końcu usuń końcowe elementy -1. W drugim przykładzie długość 4 zaokrągla się w górę do 7, co pozostawia miejsce na 6 pod indeksem 6.

Każdy węzeł jest umieszczany raz, a wynik jest raz wypełniany i przycinany, co daje czas O(n) dla tablicy o długości n. Wynik zajmuje O(n) pamięci, a stos wywołań O(h), najwyżej 14 ramek w tym przypadku, dzięki czemu rekurencja jest bezpieczna w tym zadaniu.

Algorytm

Zaokrąglij długość w górę do size = 2^k - 1 i wypełnij tablicę wyjściową o tym rozmiarze wartościami -1.
Napisz place(src, dst): jeśli src wykracza poza koniec lub tree[src] ma wartość -1, zakończ.
W przeciwnym razie ustaw out[dst] = tree[src], a następnie wywołaj place(2*src+1, 2*dst+2) i place(2*src+2, 2*dst+1).
Wywołaj place(0, 0), usuń końcowe wpisy -1 i zwróć wynik.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

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

Przeszukiwanie wszerz z kolejką par indeksów

Intuicja

Te same pary działają bez rekurencji. Umieść (0, 0) w kolejce: korzeń i miejsce, do którego trafia. Pobierz parę (src, dst) z początku kolejki, skopiuj tree[src] do out[dst] i dodaj do kolejki każde rzeczywiste dziecko wraz z zamienionym miejscem docelowym: lewe dziecko 2*src+1 z 2*dst+2, prawe dziecko 2*src+2 z 2*dst+1.

To klasyczne odwracanie iteracyjne. W przypadku obiektów węzłów pobierasz węzeł z kolejki, zamieniasz miejscami jego dwoje dzieci i dodajesz je do kolejki. Tutaj zamiana jest zapisywana pod indeksem docelowym, ponieważ tablica nie może zamienić miejscami dwóch całych poddrzew w jednym kroku. Każdy rzeczywisty węzeł trafia do kolejki raz, niosąc dokładne miejsce, do którego należy, więc wynik zawiera każdy węzeł na jego lustrzanym miejscu. W pierwszym przykładzie otrzymujemy pary (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

Złożoność czasowa wynosi O(n). Kolejka przechowuje najwyżej jeden poziom i trochę więcej, czyli O(w) dla najszerszego poziomu w, oprócz wyniku o rozmiarze O(n). Nie ma stosu wywołań, który mógłby się przepełnić, więc ta wersja bez zmian sprawdza się również w przypadku głębokich drzew opartych na wskaźnikach.

Algorytm

Zaokrąglij długość w górę do pełnych poziomów i wypełnij tablicę wyjściową o takim rozmiarze wartościami -1.
Umieść parę (0, 0) w kolejce.
Weź parę (src, dst) z początku kolejki i ustaw out[dst] = tree[src].
Dodaj do kolejki (2*src+1, 2*dst+2) i (2*src+2, 2*dst+1) dla każdego dziecka, które znajduje się w tablicy i nie ma wartości -1.
Gdy kolejka będzie pusta, usuń końcowe elementy -1 i zwróć wynik.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Pułapki i przypadki brzegowe

Samo odbicie lustrzane łatwo opisać. Błędy wynikają z tablicy: jej rozmiaru, końca oraz tego, co tak naprawdę przenosi zamiana dwóch elementów.

Zamiana miejscami tree[2*i+1] i tree[2*i+2] bezpośrednio w tablicy. Zamienia to dwie wartości, ale nie poddrzewa pod nimi. Zamiana indeksów 1 i 2 w pierwszym przykładzie pozostawia 1 i 4 pod 8.
Utworzenie wyniku o takiej samej długości jak dane wejściowe. Odbity węzeł może trafić poza ostatni indeks danych wejściowych, tak jak 6 w drugim przykładzie. Dopasuj rozmiar wyniku do pełnych poziomów.
Zapomnienie o obcięciu wyniku. Odpowiedź nie zawiera na końcu -1 — dotyczy to zarówno uzupełnionych danych wejściowych, jak i drzew, których odbicie kończy się wcześniej niż dane wejściowe.
Odwrócenie całej tablicy. Miesza to poziomy: ostatni liść stałby się korzeniem.
Pominięcie sprawdzania zakresu. Indeks potomka może wykraczać poza koniec danych wejściowych, ponieważ tablica może kończyć się zaraz za ostatnim węzłem.
Pomylenie przesunięcia w Lua i R, gdzie tablice zaczynają się od 1. Zachowaj indeksy od 0 na potrzeby działania 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania4

Czym oznacza odwrócenie drzewa binarnego?

Odwrócenie drzewa binarnego tworzy jego lustrzane odbicie: w każdym węźle lewe i prawe poddrzewo zamieniają się miejscami. Korzeń pozostaje na swoim miejscu, najbardziej lewy liść staje się najbardziej prawym, a lewy łańcuch staje się prawym. Dwukrotne odwrócenie przywraca pierwotne drzewo.

Jaka jest złożoność czasowa odwracania drzewa binarnego?

Każdy węzeł jest odwiedzany raz, więc złożoność czasowa wynosi O(n). Rozwiązanie rekurencyjne wykorzystuje O(h) miejsca na stosie dla drzewa o głębokości h, a rozwiązanie oparte na kolejce wykorzystuje O(w) dla najszerszego poziomu. W tej wersji z tablicą sama odpowiedź jest nową tablicą, co dodaje O(n).

Jak odwrócić drzewo binarne bez rekurencji?

Użyj kolejki lub stosu. Zacznij od korzenia i za każdym razem, gdy wyjmiesz węzeł, zamień miejscami jego lewe i prawe dziecko, a następnie dodaj dzieci do kolejki lub stosu. Każdy węzeł zamieniasz raz, w dowolnej kolejności, w jakiej struktura je udostępnia. W wersji tablicowej zamiast tego dodajesz do kolejki pary indeksów i zapisujesz każdy węzeł bezpośrednio w jego lustrzanym miejscu.

Dlaczego odwrócenie drzewa binarnego odwraca każdy poziom?

Odbicie zamienia miejscami lewą i prawą stronę wszędzie, więc węzły na każdym poziomie pojawiają się w odwrotnej kolejności. Przy przechowywaniu w kolejności poziomami oznacza to, że fragment tablicy odpowiadający każdemu poziomowi jest odwrócony: fragment [1, 4, -1, 9] z pierwszego przykładu daje w wyniku [9, -1, 4, 1]. Odwrócenie każdego poziomu po uzupełnieniu ostatniego o -1 to trzecie rozwiązanie o złożoności O(n), które działa tylko dla tego układu tablicy.

Python

def invertTree(tree):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

[5, 8, 3, 9, -1, 4, 1]