Symmetric Tree

Q: Jaka jest złożoność czasowa problemu drzewa symetrycznego?

Każdy rzeczywisty węzeł jest porównywany raz, jako część jednej lustrzanej pary, więc czas wynosi O(n) . Wersje rekurencyjna i stosowa wykorzystują dodatkową pamięć O(h) na oczekujące pary wzdłuż bieżącej ścieżki. Wersja poziom po poziomie przechowuje w pamięci jeden poziom, czyli O(w) dla najszerszego poziomu.

Q: Jak sprawdzić, czy drzewo binarne jest symetryczne, bez użycia rekurencji?

Utrzymuj stos lub kolejkę par węzłów, które muszą być swoimi lustrzanymi odbiciami, zaczynając od dwojga dzieci korzenia. Wyjmij parę, zakończ niepowodzeniem w przypadku niezgodności i dodaj parę zewnętrzną oraz parę wewnętrzną ich dzieci. Jeśli stos się opróżni i nie wystąpi niezgodność, drzewo jest symetryczne.

Q: Czym różni się drzewo symetryczne od dwóch identycznych drzew?

Dwa drzewa są identyczne, gdy porównasz lewą stronę z lewą, a prawą z prawą. Drzewo jest symetryczne, gdy jego lewe poddrzewo jest identyczne z lustrzanym odbiciem prawego poddrzewa, więc porównanie odbywa się na krzyż: lewa strona z prawą, a prawa z lewą. Ten sam kod sprawdzający pary rozwiązuje oba problemy, gdy zamienisz miejscami pary dzieci.

Q: Czy drzewo z jednym węzłem jest symetryczne?

Tak. Pojedynczy węzeł ma dwa puste miejsca na dzieci, a dwa puste miejsca są swoim lustrzanym odbiciem. Korzeń mający dokładnie jedno dziecko nigdy nie jest symetryczny, ponieważ to dziecko znajduje się naprzeciwko pustego miejsca.

ŁatwePrzechodzenie drzewa

+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. Zwróć true, jeśli drzewo jest swoim lustrzanym odbiciem względem pionowej linii przechodzącej przez korzeń, a w przeciwnym razie zwróć false. Zarówno kształt, jak i wartości muszą być zgodne.

Funkcja

isSymmetric(tree: integer-array) → boolean

treeinteger-array: drzewo binarne w kolejności poziomów, z -1 oznaczającym puste miejsce
Zwracaboolean: true, jeśli drzewo jest lustrzane, w przeciwnym razie false

Ograniczenia

1 ≤ tree.length ≤ 32767
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 po ostatnim węźle.
Oboje dzieci pustego miejsca również są puste, a głębokość wynosi najwyżej 14.

Przykłady

Wejście: tree = [1, 2, 2, 3, 4, 4, 3]
Wyjście: true
Wyjaśnienie: Złóż drzewo na pół. Dwie 2 o indeksach 1 i 2 spotykają się, zewnętrzne 3 o indeksach 3 i 6 spotykają się, a wewnętrzne 4 na pozycjach 4 i 5 spotykają się.

Wejście: tree = [1, 2, 2, -1, 3, -1, 3]
Wyjście: false
Wyjaśnienie: Obie wartości 3 wiszą po prawej stronie swoich rodziców. W lustrzanym odbiciu prawe dziecko lewego 2 (indeks 4) musi być skierowane ku lewemu dziecku prawego 2 (indeks 5), a indeks 5 jest pusty.

Wejście: tree = [4, 6, 6, 5, -1, -1, 9]
Wyjście: false
Wyjaśnienie: Kształt jest lustrzanym odbiciem: indeks 3 jest naprzeciw indeksu 6 i oba zawierają węzeł. Ich wartości są różne: 5 i 9, więc drzewo nie jest symetryczne.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jeśli kształt jest lustrzanym odbiciem samego siebie, ale niektóre wartości się różnią, jaka jest najmniejsza liczba wartości węzłów, które musisz zmienić, aby drzewo było symetryczne?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Symetria jest właściwością par. Każdy węzeł ma partnera w lustrzanym miejscu po drugiej stronie korzenia, a partnerem lewego dziecka jest prawe dziecko. Dlatego nigdy nie porównujesz węzła z jego własnymi dziećmi: przechodzisz jednocześnie przez obie połowy drzewa w przeciwnych kierunkach, porównujesz kształt i wartość każdej pary i zatrzymujesz się przy pierwszej niezgodnej parze.

Porównaj każdy poziom z jego odwrotnością

Intuicja

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

Teraz przyjrzyj się drzewu poziom po poziomie. Obraz lustrzany czyta się tak samo od lewej do prawej, jak od prawej do lewej, więc każdy poziom, zapisany wraz z pustymi miejscami, musi czytać się tak samo w obu kierunkach. W pierwszym przykładzie poziomy poniżej korzenia to 2 2 oraz 3 4 4 3. W drugim są to 2 2, a następnie -1 3 -1 3, co po odwróceniu daje 3 -1 3 -1, więc odpowiedzią jest false.

Puste miejsca muszą pozostać w wierszu. Bez nich najniższy poziom w drugim przykładzie zawierałby 3 3 i przeszedłby sprawdzenie. Zapisz jeden wpis dla każdego miejsca na dziecko każdego istniejącego węzła na danym poziomie; dla pustego miejsca użyj -1. Dzieci pustych miejsc również są puste, więc niczego nie dodają. Każdy węzeł jest odwiedzany raz, zatem czas działania wynosi O(n), a w pamięci naraz przechowywany jest jeden poziom, co daje O(w) dla najszerszego poziomu o szerokości w.

Algorytm

Zacznij od listy zawierającej indeks korzenia 0.
Dla każdego indeksu na liście, od lewej do prawej, zapisz oba miejsca na dzieci: wartość dziecka, jeśli istnieje, albo -1, jeśli jest puste. Zbierz istniejące dzieci na następny poziom.
Jeśli ten wiersz miejsc na dzieci różni się od jego odwróconej wersji, zwróć false.
Przejdź do następnego poziomu i powtarzaj, aż będzie pusty, a następnie zwróć true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Rekurencja w parach lustrzanych

Intuicja

Zamiast porównywać całe poziomy, porównaj dwa poddrzewa: lewe poddrzewo korzenia, które zaczyna się od indeksu 1, i prawe poddrzewo, które zaczyna się od indeksu 2. Dwa miejsca są swoimi lustrzanymi odbiciami, gdy oba są puste albo gdy oba zawierają tę samą wartość, a ich dzieci są zamienione miejscami. Lewe dziecko jednego jest lustrzanym odbiciem prawego dziecka drugiego (zewnętrzna para), a prawe dziecko jednego jest lustrzanym odbiciem lewego dziecka drugiego (wewnętrzna para).

W pierwszym przykładzie mirrors(1, 2) porównuje dwie wartości 2, a następnie wywołuje mirrors(3, 6) dla zewnętrznych wartości 3 i mirrors(4, 5) dla wewnętrznych wartości 4. Każde z tych wywołań znajduje poniżej tylko puste miejsca i zwraca true. W drugim przykładzie mirrors(4, 5) znajduje wartość 3 pod indeksem 4, naprzeciw pustego miejsca pod indeksem 5, zwraca false, a wartość false wędruje z powrotem na górę.

Każdy rzeczywisty węzeł należy do co najwyżej jednej pary, więc złożoność czasowa wynosi O(n). Stos wywołań jest tak głęboki jak drzewo, czyli O(h), co w tym przypadku oznacza najwyżej 14 ramek.

Algorytm

Napisz mirrors(a, b). Miejsce jest puste, gdy jego indeks wykracza poza koniec lub zawiera -1. Jeśli oba miejsca są puste, zwróć true; jeśli tylko jedno z nich jest puste, zwróć false.
Jeśli tree[a] i tree[b] się różnią, zwróć false.
W przeciwnym razie zwróć mirrors(2*a+1, 2*b+2) oraz mirrors(2*a+2, 2*b+1).
Zwróć mirrors(1, 2). Korzeń bez dzieci daje dwa puste miejsca, co oznacza true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Jawny stos lustrzanych par

Intuicja

Rekurencja wymaga tylko jednej rzeczy: par, które wciąż czekają na sprawdzenie. Umieść te pary na własnym stosie, a wywołania znikną. Zacznij od pary (1, 2). Zdejmij parę ze stosu. Jeśli oba miejsca są puste, nic się pod nimi nie znajduje, więc przejdź dalej. Jeśli jedno miejsce jest puste lub wartości się różnią, drzewo nie jest symetryczne. W przeciwnym razie dodaj na stos parę zewnętrzną (2*a+1, 2*b+2) oraz parę wewnętrzną (2*a+2, 2*b+1).

Kolejność sprawdzania par nie ma znaczenia, ponieważ drzewo jest symetryczne tylko wtedy, gdy każda para do siebie pasuje. Stos daje kolejność przeszukiwania w głąb; kolejka dałaby kolejność poziomami i działałaby tak samo. Trzeci przykład kończy się na pierwszej niepasującej parze, (3, 6), która zawiera 5 i 9.

Każde zdjęcie pary ze stosu obsługuje jedną parę, a każdy rzeczywisty węzeł należy do co najwyżej jednej pary, więc złożoność czasowa wynosi O(n). Stos przechowuje około jednej oczekującej pary na każdy poziom bieżącej ścieżki, co daje O(h) pamięci, i nie trzeba martwić się limitem rekurencji.

Algorytm

Umieść parę (1, 2) na stosie.
Zdejmij parę (a, b). Jeśli oba miejsca są puste (indeks wykracza poza koniec lub wynosi -1), przejdź do następnej pary.
Jeśli tylko jedno miejsce jest puste lub tree[a] różni się od tree[b], zwróć false.
Umieść pary (2*a+1, 2*b+2) i (2*a+2, 2*b+1) na stosie.
Gdy stos będzie pusty, zwróć true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi porównuje niewłaściwą parę węzłów albo pomija fakt, że puste miejsce jest częścią kształtu drzewa.

Sprawdzanie każdego poddrzewa osobno. Lewe poddrzewo nie musi być symetryczne samo w sobie: w [1, 2, 2, 3, 4, 4, 3] poddrzewo 2, 3, 4 nie jest symetryczne, a całe drzewo jest. Lewe poddrzewo musi być lustrzanym odbiciem prawego.
Nieprawidłowe parowanie dzieci. Lewe dziecko po jednej stronie odpowiada prawemu dziecku po drugiej stronie: (2*a+1, 2*b+2) oraz (2*a+2, 2*b+1), nigdy (2*a+1, 2*b+1).
Porównywanie tylko wartości. Jeśli usuniesz puste miejsca z [1, 2, 2, -1, 3, -1, 3], każdy poziom będzie wyglądał tak samo w obu kierunkach, a mimo to drzewo nie jest symetryczne. Zachowaj -1 w wierszu poziomu albo sprawdzaj, czy miejsce jest puste, podczas testowania pary.
Odczyt poza końcem tablicy. Indeks wykraczający poza koniec tablicy oznacza puste miejsce. Sprawdź a < n przed odczytaniem tree[a]; drzewo z jednym węzłem w ogóle nie ma indeksu 1 ani 2.
Kończenie po znalezieniu pierwszej pasującej pary. Jedna poprawna para niczego nie dowodzi; zwróć true dopiero po sprawdzeniu każdej pary.
Pomylenie przesunięcia w Lua i R, gdzie tablice zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 na potrzeby działania 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu drzewa symetrycznego?

Każdy rzeczywisty węzeł jest porównywany raz, jako część jednej lustrzanej pary, więc czas wynosi O(n). Wersje rekurencyjna i stosowa wykorzystują dodatkową pamięć O(h) na oczekujące pary wzdłuż bieżącej ścieżki. Wersja poziom po poziomie przechowuje w pamięci jeden poziom, czyli O(w) dla najszerszego poziomu.

Jak sprawdzić, czy drzewo binarne jest symetryczne, bez użycia rekurencji?

Utrzymuj stos lub kolejkę par węzłów, które muszą być swoimi lustrzanymi odbiciami, zaczynając od dwojga dzieci korzenia. Wyjmij parę, zakończ niepowodzeniem w przypadku niezgodności i dodaj parę zewnętrzną oraz parę wewnętrzną ich dzieci. Jeśli stos się opróżni i nie wystąpi niezgodność, drzewo jest symetryczne.

Czym różni się drzewo symetryczne od dwóch identycznych drzew?

Dwa drzewa są identyczne, gdy porównasz lewą stronę z lewą, a prawą z prawą. Drzewo jest symetryczne, gdy jego lewe poddrzewo jest identyczne z lustrzanym odbiciem prawego poddrzewa, więc porównanie odbywa się na krzyż: lewa strona z prawą, a prawa z lewą. Ten sam kod sprawdzający pary rozwiązuje oba problemy, gdy zamienisz miejscami pary dzieci.

Czy drzewo z jednym węzłem jest symetryczne?

Tak. Pojedynczy węzeł ma dwa puste miejsca na dzieci, a dwa puste miejsca są swoim lustrzanym odbiciem. Korzeń mający dokładnie jedno dziecko nigdy nie jest symetryczny, ponieważ to dziecko znajduje się naprzeciwko pustego miejsca.

Python

def isSymmetric(tree):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

tree = [1, 2, 2, 3, 4, 4, 3]

Oczekiwane

true

Symmetric Tree

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Porównaj każdy poziom z jego odwrotnością

Rekurencja w parach lustrzanych

Jawny stos lustrzanych par

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania