Kth Smallest Element in a BST
Дано бинарное дерево поиска в виде массива root в порядке кучи: корень находится по индексу 0, дети узла с индексом i находятся по индексам 2*i+1 (слева) и 2*i+2 (справа), а -1 обозначает пустое место. В конце массива могут находиться дополнительные элементы -1. В каждом узле левое поддерево содержит только меньшие значения, а правое — только большие.
Верни k-е наименьшее значение в дереве, считая с 1.
Функция
- rootinteger-array
- двоичное дерево поиска в порядке уровней, где -1 обозначает пустое место
- kinteger
- позиция, которую нужно найти в порядке возрастания, начиная с 1
- Возвращаетinteger
- k-е наименьшее значение в дереве
Ограничения
1 ≤ root.length ≤ 32767- Каждый
root[i]равен-1или значению, для которого0 ≤ root[i] ≤ 105. root[0]никогда не равно-1, поэтому в дереве есть как минимум один узел.- После последнего узла в конце массива могут быть дополнительные элементы
-1. - Оба потомка пустого места тоже пусты, а глубина не превышает
14. - Правило упорядочивания выполняется в каждом узле, поэтому ни одно значение не встречается дважды.
1 ≤ k ≤количество узлов в дереве.
Примеры
- Ввод
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Вывод
- 29
- Пояснение
- В порядке возрастания значения:
6, 17, 22, 29, 41, 65, 90, а четвёртое —29. Это наибольшее из четырёх значений в левом поддереве корня.
- Ввод
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Вывод
- 2
- Пояснение
- Наименьшее значение завершает путь, который продолжается влево:
12,5,2.7под9и дополнение-1этого не меняют.
Дополнительный вопрос
Если дерево часто изменяется и вас много раз просят найти значение, которое является k-м по величине, что можно хранить в каждом узле, чтобы каждый запрос занимал O(h)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Какой способ обхода бинарного дерева поиска перечисляет его значения от наименьшего к наибольшему?
Обход левого поддерева, затем узла, затем правого поддерева даёт значения в отсортированном порядке. Ответом будет
k-е значение, полученное при обходе, поэтому можно остановиться на нём.Используй стек. Начиная с текущего узла, добавляй узлы в стек, двигаясь к левому потомку. Извлеки верхний узел и посчитай его; остановись на
k-м извлечении. Иначе перейди к правому потомку извлечённого узла по индексу2*i+2и повтори.
Решение
Симметричный обход (левое поддерево, узел, правое поддерево) считывает значения бинарного дерева поиска в порядке возрастания, поэтому ответом будет k-е достигнутое значение. Выполни обход с помощью собственного стека и остановись на нём; сортировка не нужна.
Соберите все значения и отсортируйте
Идея
Не обращай внимания на форму: оставь все элементы, которые не равны -1, отсортируй их и верни элемент на позиции k-1. Для первого примера отсортированный список выглядит так: 6, 17, 22, 29, 41, 65, 90, а на позиции 3 находится 29.
Этот способ работает для любого дерева, упорядоченного или нет. В этом же его недостаток: он игнорирует уже имеющийся порядок в дереве и требует O(n log n) времени на сортировку и O(n) памяти для копии.
Алгоритм
- Соберите все элементы
root, которые не равны-1. - Отсортируйте собранные значения по возрастанию.
- Верните значение на позиции
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]Симметричный обход в список
Идея
Под любым узлом в левом поддереве находятся только меньшие значения, а в правом — только большие. Обойдите левое поддерево, затем узел, затем правое поддерево и повторите то же для каждого поддерева: каждый узел окажется после всех меньших значений и перед всеми большими, поэтому результат будет отсортирован. В первом примере обход даёт 6, 17, 22, 29, 41, 65, 90.
Один проход заменяет сортировку: время O(n) и O(n) памяти для списка. При этом обходится всё дерево, даже при k = 1, когда ответ находится в конце самого левого пути.
Алгоритм
- Напиши
inorder(i): вернись, если место пустое (за концом или-1). - В противном случае вызови
inorder(2*i+1), добавьroot[i]в список, затем вызовиinorder(2*i+2). - Вызови
inorder(0). - Верни элемент списка на позиции
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 sortedИтеративный симметричный обход с остановкой на k
Идея
Явный стек позволяет остановить обход на середине. Иди влево, насколько возможно, помещая в стек каждый узел. Узел на вершине — это наименьшее значение, которое ещё не было учтено, потому что всё меньшее находится в его левом поддереве, которое пусто или уже учтено. Извлеки его из стека и учти; следующим в отсортированном порядке идёт его правое поддерево.
Для k = 4 в первом примере: помести в стек 41, 17, 6. Извлеки из стека 6, затем 17 и перейди к его правому потомку: помести в стек 29 и 22. Извлеки из стека 22, затем 29 — это четвёртое значение. Обход не затрагивает 65 или 90.
Стек содержит не более одного узла на каждом уровне, поэтому занимаемое пространство составляет O(h). Обход один раз спускается вниз, а затем выполняет извлечение из стека k раз: время O(h + k).
Алгоритм
- Начни с пустого стека и
i = 0. - Пока
iявляется реальным узлом, добавляй его в стек и переходи к2*i+1. - Извлеки верхний элемент в
iи вычти1изk. - Если теперь
kравен0, верниroot[i]. - Иначе перейди к
2*i+2и вернись к шагу 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
Ловушки и крайние случаи
- Чтение массива по порядку индексов. Порядок обхода по уровням не отсортирован: первый пример начинается с
41, 17, 65. - Ошибка на единицу для
k. Отсчёт начинается с1: верните элемент списка на позицииk-1и остановите обход, когда счётчик достигнетk. - Пропуск правого поддерева после извлечения элемента. Во втором примере
9и7находятся в правом поддереве5, и при таком обходе они никогда не будут учтены. - Считать отсутствующего потомка реальным. Потомок отсутствует, если его индекс выходит за пределы массива или по этому индексу находится
-1:22находится по индексу9, поэтому его потомки19и20выходят за пределы массива. - В Lua и R индексация массивов начинается с 1. Оставляйте индексы узлов с отсчётом от 0 для
2*i+1и обращайтесь кroot[i + 1].
Частые вопросы3
Какова временная сложность поиска k-го наименьшего элемента в BST?
Итеративный обход в симметричном порядке занимает время O(h + k) и требует дополнительной памяти O(h) для дерева глубины h. В худшем случае, когда k = n или дерево имеет форму цепочки, это O(n).
Как найти k-й наибольший элемент в BST?
Зеркально обойдите дерево: сначала правое поддерево, затем узел, потом левое поддерево. Так значения будут перечислены в порядке убывания. Идите вправо как можно дальше, добавляя узлы в стек, извлекайте узел из стека и считайте, а после каждого извлечения переходите к левому потомку. При k-м извлечении вы получите k-е по величине значение.
Как остановить рекурсивный симметричный обход на k-м значении?
Храните счётчик вне рекурсии, начиная со значения k. Вычитайте 1 после возврата из левого поддерева узла и записывайте значение узла, когда счётчик достигает 0. После каждого вызова сразу возвращайтесь, если ответ уже записан. Тогда рекурсия будет соответствовать версии со стеком: время O(h + k), память O(h).
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def kthSmallest(root, k):
# Напишите код здесьТест #1
Тест #2
Аргументы
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Ожидаемый вывод
29