Validate Binary Search Tree
Drzewo binarne jest przechowywane w tablicy tree w porządku kopca: 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.
Napisz isValidBST, które zwraca true, jeśli drzewo jest binarnym drzewem wyszukiwań, a w przeciwnym razie false. W binarnym drzewie wyszukiwań wartość każdego węzła jest ściśle większa od każdej wartości w jego lewym poddrzewie i ściśle mniejsza od każdej wartości w jego prawym poddrzewie.
Funkcja
- treeinteger-array
- drzewo binarne w kolejności poziomami, z wartością -1 oznaczającą puste miejsce
- Zwracaboolean
- true, jeśli drzewo jest binarnym drzewem wyszukiwania, w przeciwnym razie false
Ograniczenia
1 ≤ tree.length ≤ 32767- Każde
tree[i]to-1lub wartość spełniająca warunek0 ≤ tree[i] ≤ 105. 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
-1po ostatnim węźle. - Oboje dzieci pustego miejsca również są puste, a głębokość wynosi najwyżej
14. - Wartości mogą się powtarzać.
Przykłady
- Wejście
- tree = [8, 3, 12, 1, 6, 10, 15]
- Wyjście
- true
- Wyjaśnienie
- Odczytane w kolejności (lewe poddrzewo, węzeł, prawe poddrzewo) wartości to
1, 3, 6, 8, 10, 12, 15. Ściśle rosną, więc każdy węzeł znajduje się po właściwej stronie każdego przodka.
- Wejście
- tree = [10, 5, 15, -1, -1, 6, 20]
- Wyjście
- false
- Wyjaśnienie
- Każdy węzeł jest większy od swojego lewego dziecka i mniejszy od prawego, jednak
6o indeksie5znajduje się w prawym poddrzewie korzenia, więc musi być większe od10.
- Wejście
- tree = [12, 7, 12]
- Wyjście
- false
- Wyjaśnienie
- Prawe dziecko korzenia zawiera
12, czyli tyle samo co korzeń. Prawe poddrzewo musi być ściśle większe, więc drzewo nie spełnia warunku.
Pytanie dodatkowe
Rodzic węzła znajduje się pod indeksem (i-1)/2, zaokrąglonym w dół. Czy potrafisz przejść drzewo w odpowiedniej kolejności, używając dodatkowej pamięci O(1) i przemieszczając się przez rodziców zamiast używać stosu lub rekurencji?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
W
[10, 5, 15, -1, -1, 6, 20]każdy węzeł jest większy od swojego lewego dziecka i mniejszy od prawego. Dlaczego mimo to nie jest to drzewo wyszukiwań?Każdy przodek wyznacza granicę dla węzła: od dołu, jeśli węzeł znajduje się po jego lewej stronie, a od góry, jeśli znajduje się po jego prawej stronie. Razem te granice tworzą jeden otwarty przedział. Przejście w lewo od wartości
vobniża górną granicę dov; przejście w prawo podnosi dolną granicę dov.Przechowuj stos
(index, low, high), zaczynając od korzenia i zakresu szerszego niż każda dozwolona wartość. Zdejmij element ze stosu, zwróć błąd, jeśli wartość nie mieści się ściśle w zakresie, i dodaj każde istniejące dziecko wraz z zawężonym zakresem.
Rozwiązanie
Ta reguła dotyczy całych poddrzew, więc porównywanie każdego węzła z jego dwójką dzieci nie wystarczy: węzeł położony głęboko może naruszyć ograniczenie ustalone przez przodka znajdującego się kilka poziomów wyżej. Możesz odczytać drzewo w kolejności i sprawdzić, czy wartości ściśle rosną, albo przekazywać każdemu węzłowi zakres dozwolony przez jego przodków.
Porównaj każdy węzeł z całymi jego poddrzewami
Intuicja
Każda wartość w lewym poddrzewie węzła jest mniejsza od jego wartości v dokładnie wtedy, gdy największa wartość w tym poddrzewie jest mniejsza od v, a każda wartość w prawym poddrzewie jest większa od v dokładnie wtedy, gdy najmniejsza wartość w tym poddrzewie jest większa od v. Dwie funkcje pomocnicze rekurencyjnie znajdują te wartości. Puste poddrzewo zwraca -1 lub 100001, czyli wartość spoza zakresu wartości, więc nigdy nie spowoduje błędu.
Każdy węzeł jest skanowany raz dla każdego przodka, co daje około n × h odwiedzin dla drzewa o głębokości h. Przy głębokości nie większej niż 14 jest to niewielki koszt, ale w przypadku ścieżki złożonej z n węzłów rośnie do O(n²).
Algorytm
- Przejdź przez każdy indeks
i, którego wartość nie jest równa-1. - Znajdź największą wartość w lewym poddrzewie pod indeksem
2*i+1(-1, jeśli jest puste) oraz najmniejszą w prawym poddrzewie pod indeksem2*i+2(100001, jeśli jest puste). - Jeśli największa wartość jest większa lub równa
tree[i]albo najmniejsza jest mniejsza lub równatree[i], zwróćfalse. - Zwróć
true.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return TrueWartości w kolejności inorder muszą ściśle rosnąć
Intuicja
Przejście inorder odwiedza lewe poddrzewo, następnie węzeł, a potem prawe poddrzewo, więc w drzewie wyszukiwań binarnych odczytuje wartości w posortowanej kolejności.
Odwrotna zależność też zachodzi. Dla dowolnego węzła v całe jego lewe poddrzewo znajduje się w sekwencji bezpośrednio przed nim, a całe prawe poddrzewo — bezpośrednio po nim. Jeśli sekwencja jest ściśle rosnąca, każda wartość przed v jest mniejsza, a każda wartość po nim jest większa, więc reguła jest spełniona dla v i tak samo dla każdego węzła.
Drugi przykład daje sekwencję 5, 10, 6, 15, 20: spadek z 10 do 6 ujawnia nieprawidłowo umieszczony węzeł. Każdy węzeł jest odwiedzany raz: czas O(n) i pamięć O(n) na listę.
Algorytm
- Napisz
walk(i): jeśli miejsce jest puste, zakończ; w przeciwnym razie przejdź do2*i+1, dodajtree[i], a następnie przejdź do2*i+2. - Wywołaj
walk(0), aby zebrać wartości w kolejności. - Dla każdej pozycji
kod1, jeślivalues[k-1] ≥ values[k], zwróćfalse. - Zwróć
true.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return TruePrzekazuj dozwolony zakres w dół drzewa
Intuicja
Każdy przodek nakłada jedno ograniczenie na węzeł: poniżej a, jeśli węzeł znajduje się w lewym poddrzewie przodka zawierającego a, powyżej a, jeśli znajduje się w prawym poddrzewie. Razem ograniczenia tworzą jeden otwarty przedział (low, high), a węzeł znajduje się we właściwym miejscu dokładnie wtedy, gdy jego wartość leży ściśle wewnątrz tego przedziału.
Twórz przedział podczas schodzenia w dół. Lewe dziecko zachowuje low i otrzymuje high = v; prawe dziecko zachowuje high i otrzymuje low = v. W drugim przykładzie 15 przekazuje swojemu lewemu dziecku przedział (10, 15), a 6 od razu nie spełnia warunku. Wartości mieszczą się w przedziale od 0 do 10^5, więc -1 i 100001 służą jako brak ograniczenia. Każdy węzeł jest sprawdzany raz, czas działania wynosi O(n), a na stosie znajduje się O(h) węzłów.
Algorytm
- Umieść na stosie
(0, -1, 100001): korzeń, bez rzeczywistego ograniczenia. - Zdejmij ze stosu
(i, low, high). Jeślitree[i]nie znajduje się ściśle międzylowahigh, zwróćfalse. - Umieść na stosie każde istniejące dziecko: lewe pod indeksem
2*i+1z(low, tree[i]), prawe pod indeksem2*i+2z(tree[i], high). - Gdy stos będzie pusty, zwróć
true.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
Pułapki i przypadki brzegowe
- Porównywanie węzła tylko z jego dziećmi. W
[10, 5, 15, -1, -1, 6, 20]każda para rodzic–dziecko wygląda poprawnie, ale6narusza ograniczenie korzenia. - Dopuszczanie równych wartości.
[12, 7, 12]jest nieprawidłowe: porównuj za pomocą<, nigdy≤. - Używanie
0jako dolnego „braku ograniczenia”. Odrzuca to prawidłowe drzewo[0]. - Odczytywanie dziecka bez sprawdzenia
2*i+1 < tree.length. W[12, 7, 12]indeks3znajduje się poza końcem. - W Lua i R tablice zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 na potrzeby
2*i+1i odczytujtree[i + 1].
Najczęstsze pytania3
Caka jest złożoność czasowa sprawdzania poprawności binarnego drzewa wyszukiwań?
Sprawdzenie porządku inorder i sprawdzenie zakresu odwiedzają każdy węzeł raz: czas O(n), a sprawdzenie zakresu wymaga dodatkowo O(h) miejsca na stos dla drzewa o głębokości h. Porównywanie każdego węzła z całymi jego poddrzewami kosztuje O(n × h), co dla drzewa w kształcie ścieżki osiąga O(n²).
Czy potrafisz zweryfikować BST za pomocą przejścia inorder bez przechowywania każdej wartości?
Tak. Sprawdzenie porównuje każdą wartość tylko z poprzednią, więc zamiast listy przechowuj poprzednią wartość w zmiennej i zwróć false w chwili, gdy wartość nie jest większa. Dodatkowe zużycie pamięci spada do O(h) na potrzeby rekurencji lub stosu.
Czy drzewo wyszukiwań binarnych może zawierać zduplikowane wartości?
Nie według ścisłej definicji używanej tutaj: równa wartość nie pasuje po żadnej ze stron. Niektóre podręczniki dopuszczają równe wartości po jednej ze stron, na przykład po prawej. Zgodnie z tą zasadą jedno ścisłe porównanie zmienia się na ≤.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def isValidBST(tree):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
tree = [8, 3, 12, 1, 6, 10, 15]
Oczekiwany wynik
true