Kth Smallest Element in a BST
Otrzymujesz binarne drzewo wyszukiwań jako tablicę root w porządku kopcowym: 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), a -1 oznacza puste miejsce. Tablica może kończyć się dodatkowymi wpisami -1. W każdym węźle lewe poddrzewo zawiera wyłącznie mniejsze wartości, a prawe poddrzewo — wyłącznie większe.
Zwróć k-tą najmniejszą wartość w drzewie, licząc od 1.
Funkcja
- rootinteger-array
- drzewo wyszukiwań binarnych w kolejności poziomami, z -1 oznaczającym puste miejsce
- kinteger
- pozycja do znalezienia w kolejności rosnącej, zaczynając od 1
- Zwracainteger
- k-ta najmniejsza wartość w drzewie
Ograniczenia
1 ≤ root.length ≤ 32767- Każde
root[i]ma wartość-1albo wartość spełniającą warunek0 ≤ root[i] ≤ 105. 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
-1po ostatnim węźle. - Oboje dzieci pustego miejsca również są puste, a głębokość wynosi co najwyżej
14. - Reguła porządku obowiązuje w każdym węźle, więc żadna wartość nie pojawia się dwukrotnie.
1 ≤ k ≤liczba węzłów w drzewie.
Przykłady
- Wejście
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Wyjście
- 29
- Wyjaśnienie
- W kolejności rosnącej wartości to
6, 17, 22, 29, 41, 65, 90, a czwarta z nich to29. Jest to największa z czterech wartości w lewym poddrzewie korzenia.
- Wejście
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Wyjście
- 2
- Wyjaśnienie
- Najmniejsza wartość kończy ścieżkę, która biegnie dalej w lewo:
12,5,2.7pod9i dopełnienie-1tego nie zmieniają.
Pytanie dodatkowe
Jeśli drzewo często się zmienia i wiele razy trzeba znaleźć k-tą najmniejszą wartość, co mogłoby przechowywać każde węzeł, aby każde zapytanie zajmowało O(h)?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Który sposób przechodzenia po drzewie wyszukiwań binarnych wypisuje jego wartości od najmniejszej do największej?
Odwiedzenie lewego poddrzewa, następnie węzła, a potem prawego poddrzewa daje kolejność posortowaną. Odpowiedzią jest
k-ta wartość uzyskana podczas tego przejścia, więc możesz się na niej zatrzymać.Użyj stosu. Z bieżącego węzła odkładaj węzły na stos, przechodząc do lewego dziecka. Zdejmij element ze szczytu i zwiększ licznik; zatrzymaj się przy
k-tym zdjęciu. W przeciwnym razie przejdź do prawego dziecka zdjętego węzła pod indeksem2*i+2i powtórz.
Rozwiązanie
Przejście w porządku inorder (lewe poddrzewo, węzeł, prawe poddrzewo) odczytuje wartości drzewa wyszukiwań binarnych w kolejności rosnącej, więc k-ta osiągnięta wartość jest odpowiedzią. Wykonaj przejście, używając własnego stosu, i zatrzymaj się w tym miejscu; sortowanie nie jest potrzebne.
Zbierz wszystkie wartości i posortuj
Intuicja
Zignoruj strukturę: zachowaj każdy element, który nie jest równy -1, posortuj je i zwróć element z pozycji k-1. W pierwszym przykładzie posortowana lista to 6, 17, 22, 29, 41, 65, 90, a na pozycji 3 znajduje się 29.
To rozwiązanie jest poprawne dla każdego drzewa, uporządkowanego lub nie. Na tym polega też jego koszt: ignoruje istniejący porządek drzewa i wymaga O(n log n) na sortowanie oraz O(n) pamięci na kopię.
Algorytm
- Zbierz każdy element
root, który nie jest równy-1. - Posortuj zebrane wartości rosnąco.
- Zwróć wartość na pozycji
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Przejście inorder do listy
Intuicja
Pod każdym węzłem lewe poddrzewo zawiera tylko mniejsze wartości, a prawe poddrzewo tylko większe. Odwiedź lewe poddrzewo, następnie węzeł, a potem prawe poddrzewo. Tak samo postępuj w każdym poddrzewie: każdy węzeł trafia po wszystkich mniejszych wartościach i przed wszystkimi większymi, więc wynik jest posortowany. W pierwszym przykładzie przejście daje 6, 17, 22, 29, 41, 65, 90.
Jedno przejście zastępuje sortowanie: czas O(n) i pamięć O(n) na listę. Nadal odwiedza całe drzewo, nawet dla k = 1, gdy odpowiedź znajduje się na końcu skrajnej lewej ścieżki.
Algorytm
- Napisz
inorder(i): zakończ działanie w pustym miejscu (za końcem lub przy-1). - W przeciwnym razie wywołaj
inorder(2*i+1), dodajroot[i]do listy, a następnie wywołajinorder(2*i+2). - Wywołaj
inorder(0). - Zwróć element listy na pozycji
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedIteracyjne przejście in-order, które zatrzymuje się przy k
Intuicja
Jawny stos pozwala przerwać przechodzenie w dowolnym momencie. Idź w lewo tak daleko, jak to możliwe, odkładając każdy węzeł na stos. Węzeł na szczycie jest najmniejszą wartością, której jeszcze nie uwzględniono, ponieważ wszystko mniejsze znajduje się w jego lewym poddrzewie, które jest puste lub zostało już uwzględnione. Zdejmij go ze stosu i uwzględnij; następne w kolejności rosnącej jest jego prawe poddrzewo.
Dla k = 4 w pierwszym przykładzie: odłóż na stos 41, 17, 6. Zdejmij 6, potem 17 i przejdź do jego prawego dziecka: odłóż na stos 29 i 22. Zdejmij 22, a potem 29 — czwartą wartość. Przechodzenie nigdy nie obejmuje 65 ani 90.
Stos zawiera najwyżej jeden węzeł na poziom, więc złożoność pamięciowa wynosi O(h). Przechodzenie schodzi w dół raz, a następnie wykonuje k operacji zdejmowania ze stosu: czas O(h + k).
Algorytm
- Zacznij od pustego stosu i
i = 0. - Dopóki
iwskazuje rzeczywisty węzeł, umieść go na stosie i przejdź do2*i+1. - Zdejmij element ze szczytu stosu i przypisz go do
i, a następnie odejmij1odk. - Jeśli
kwynosi teraz0, zwróćroot[i]. - W przeciwnym razie przejdź do
2*i+2i wróć do kroku 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Pułapki i przypadki brzegowe
- Odczytywanie tablicy według indeksów. Poziomy nie są posortowane: pierwszy przykład zaczyna się od
41, 17, 65. - Błąd o jeden przy
k. Liczenie zaczyna się od1: zwróć element z pozycjik-1na liście i zakończ przechodzenie, gdy licznik osiągniek. - Pomijanie prawego poddrzewa po zdjęciu elementu ze stosu. W drugim przykładzie
9i7znajdują się w prawym poddrzewie5, więc podczas przechodzenia nigdy nie zostaną uwzględnione w liczeniu. - Traktowanie brakującego dziecka jako istniejącego. Dziecko jest puste, gdy jego indeks wykracza poza koniec tablicy lub zawiera
-1:22znajduje się pod indeksem9, więc jego dzieci19i20wykraczają poza koniec tablicy. - Tablice w Lua i R zaczynają się od 1. Zachowaj indeksy węzłów liczone od 0 dla
2*i+1i odczytujroot[i + 1].
Najczęstsze pytania3
Jaka jest złożoność czasowa znajdowania k-tego najmniejszego elementu w BST?
Iteracyjne przejście w porządku inorder zajmuje O(h + k) czasu i wymaga O(h) dodatkowej pamięci dla drzewa o głębokości h. W najgorszym przypadku, gdy k = n lub drzewo ma kształt ścieżki, jest to O(n).
Jak znaleźć k-ty największy element w BST?
Odbij kolejność przechodzenia: prawe poddrzewo, potem węzeł, a następnie lewe poddrzewo. W ten sposób wypiszesz wartości w kolejności malejącej. Idź jak najdalej w prawo, dodając węzły na stos, zdejmij węzeł ze stosu i zwiększ licznik, a po każdym zdjęciu przejdź do lewego dziecka. k-te zdjęcie ze stosu oznacza k-tą największą wartość.
Jak zatrzymać rekurencyjne przechodzenie w porządku inorder na k-tej wartości?
Umieść licznik poza rekurencją, zaczynając od k. Odejmij 1 po powrocie z lewego poddrzewa węzła i zapisz wartość węzła, gdy licznik osiągnie 0. Po każdym wywołaniu od razu zwracaj wynik, jeśli został już zapisany. Rekurencja ma wtedy taką samą złożoność jak wersja ze stosem: czas O(h + k), pamięć O(h).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def kthSmallest(root, k):
# Wpisz tutaj kodTest #1
Test #2
Argumenty
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Oczekiwany wynik
29