Balanced Binary Tree

+10

Tablica root przechowuje drzewo binarne. 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 dodatkowe wpisy -1 mogą znajdować się na końcu.

Zwróć true, jeśli drzewo jest zrównoważone pod względem wysokości, co oznacza, że w każdym węźle wysokości lewego i prawego poddrzewa różnią się najwyżej o 1, a w przeciwnym razie zwróć false. Wysokość poddrzewa to liczba węzłów na jego najdłuższej ścieżce w dół; puste poddrzewo ma wysokość 0.

Funkcja

isBalanced(root: integer-array) → boolean

rootinteger-array: drzewo binarne w kolejności poziomami, z wartością -1 w pustych miejscach
Zwracaboolean: prawda, jeśli wysokości dwóch poddrzew każdego węzła różnią się najwyżej o 1, w przeciwnym razie fałsz

Ograniczenia

1 ≤ root.length ≤ 32767
Każde root[i] ma wartość -1 lub 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 co najwyżej 14.
Wartości węzłów są różne.

Przykłady

Wejście: root = [5, 2, 9, -1, -1, 7, 11]
Wyjście: true
Wyjaśnienie: Lewe poddrzewo korzenia to pojedynczy węzeł 2 o wysokości 1. Jego prawe poddrzewo, zawierające węzły 9, 7, 11, ma wysokość 2. Różnią się o 1, a każdy inny węzeł ma dwa poddrzewa o równej wysokości.

Wejście: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Wyjście: false
Wyjaśnienie: Obie strony korzenia mają wysokość 3, ale węzeł 3 nie spełnia warunku: jego lewe poddrzewo 1, 0 ma wysokość 2, a prawe jest puste.

Wejście: root = [4, 2, -1, 1]
Wyjście: false
Wyjaśnienie: Korzeń ma łańcuch 2, 1 po lewej stronie, wysokość 2, a po prawej stronie nic, wysokość 0. Różnica wynosząca 2 jest zbyt duża.

Pytanie dodatkowe

Czy możesz sprawdzić drzewo bez rekurencji, używając jawnego stosu?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Ta reguła obowiązuje w każdym węźle, więc drzewo, którego korzeń wygląda na parzysty, może mimo to nie spełniać jej niżej, tak jak w drugim przykładzie przy 3. Przejście post-order oblicza wysokość każdego poddrzewa tylko raz i przekazuje informację o niepowodzeniu wyżej, gdy tylko ono wystąpi, w czasie O(n).

Przelicz wysokości w każdym węźle

Intuicja

Przełóż definicję na kod. height(i) wynosi 0 w pustym miejscu, a w innym przypadku jest o 1 większe od wysokości wyższego dziecka. Porównaj wysokości obojga dzieci w każdym rzeczywistym węźle; pierwszy węzeł, w którym różnią się o więcej niż 1, sprawia, że odpowiedź brzmi false.

Każde sprawdzenie przechodzi przez całe poddrzewo poniżej danego węzła, więc węzeł jest odwiedzany raz dla każdego węzła powyżej niego: O(n·h). Przy maksymalnie 14 poziomach pełne drzewo liczące 16,383 węzłów wymaga około 2 × 10^5 kroków. Łańcuch n węzłów wymagałby O(n²).

Algorytm

Określ height(i) jako 0 dla indeksu poza końcem lub -1, a dla rzeczywistego węzła jako 1 + max(height(2*i+1), height(2*i+2)).
Odwiedź każdy indeks i, który zawiera rzeczywisty węzeł.
Jeśli height(2*i+1) i height(2*i+2) różnią się o więcej niż 1, zwróć false.
Jeśli pętla zakończy się bez błędu, zwróć true.

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

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Jedno przejście post-order, które zwraca wysokość lub informację o niepowodzeniu

Intuicja

Kontrola w węźle wymaga wysokości jego dwóch poddrzew, a węzeł musi też zgłosić własną wysokość. Uzyskaj więc obie wartości podczas jednego przejścia postorder: każde wywołanie zwraca wysokość swojego poddrzewa po powrocie obu dzieci.

Błąd niżej w drzewie również musi zostać przekazany w górę. Prawdziwa wysokość nigdy nie jest ujemna, więc użyj -1: wywołanie zwraca -1, gdy dziecko zwróciło -1 lub wysokości dzieci różnią się o więcej niż 1. W drugim przykładzie węzeł 3 widzi wysokości 2 i 0 i zwraca -1, a korzeń przekazuje tę wartość dalej, nie odwiedzając swojej prawej strony.

Żaden węzeł nie jest odwiedzany dwukrotnie, więc złożoność czasowa wynosi O(n), a na stosie znajduje się O(h) wywołań.

Algorytm

Napisz check(i). Jeśli indeks wykracza poza koniec lub ma wartość -1, zwróć 0.
Oblicz left = check(2*i+1). Jeśli ma wartość -1, zwróć -1.
Oblicz right = check(2*i+2). Jeśli ma wartość -1 lub wartości left i right różnią się o więcej niż 1, zwróć -1.
W przeciwnym razie zwróć 1 + max(left, right).
Zwróć informację, czy check(0) ma wartość inną niż -1.

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

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Pułapki i przypadki brzegowe

Sprawdzanie tylko korzenia. W drugim przykładzie obie strony korzenia mają wysokość 3, a mimo to węzeł 3 różni się o 2.
Porównywanie najpłytszego i najgłębszego liścia. Najmniejsze zrównoważone drzewo o wysokości 6 ma liście na głębokości 4 i 6, a każdy węzeł w nim przechodzi sprawdzanie.
Utrata informacji o błędzie podczas powrotu w górę. Jeśli potomek zwraca -1, a rodzic oblicza 1 + max(-1, 2), błąd znów zmienia się w wysokość.
Używanie długości tablicy jako wysokości. Końcowe wpisy -1 sprawiają, że tablica jest dłuższa niż głębokość drzewa.
W Lua i R indeksowanie tablic zaczyna się od 1. Zachowaj indeksy węzłów liczone od 0 dla 2*i+1 i odczytuj root[i + 1].

Najczęstsze pytania3

C jaka jest złożoność czasowa zrównoważonego drzewa binarnego?

Jedno przejście w porządku post-order odwiedza każdy węzeł raz: czas O(n) i O(h) miejsca na stosie dla drzewa o wysokości h. Ponowne obliczanie wysokości w każdym węźle kosztuje O(n·h), co w przypadku łańcucha daje O(n²).

Co oznacza, że drzewo binarne jest zrównoważone pod względem wysokości?

W każdym węźle wysokości lewego i prawego poddrzewa różnią się najwyżej o 1. Drzewa AVL przywracają tę właściwość po każdym wstawieniu i usunięciu, dzięki czemu ich wysokość wynosi O(log n).

Czy kompletne drzewo binarne jest zawsze zrównoważone?

Tak. Każdy poziom kompletnego drzewa jest pełny, z wyjątkiem ewentualnie ostatniego, który zapełnia się od lewej, więc w każdym węźle wysokości dwóch poddrzew różnią się najwyżej o 1. Odwrotna zależność nie zachodzi: zrównoważone drzewo może mieć luki po lewej stronie ostatniego poziomu.

def isBalanced(root):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, -1, -1, 7, 11]

Oczekiwany wynik

true