Kth Smallest Element in a BST

Средняя№230симметричный

Дан корень двоичного дерева поиска и число k. Нужно вернуть k-е наименьшее значение в дереве, считая с 1. Наше дерево: 13 с потомками 7 и 18; у 7 потомки 3 и 10; у 10 левый потомок 8; у 18 правый потомок 25. k = 4 — ответ 10.

230 Kth Smallest Element in a BSTРазбор · 1×

Пример: 4-е наименьшее значение двоичного дерева поиска: обходим его по порядку со стеком и останавливаемся на 4-м значении.

nonenonenonenonenonenonenonenone13718310258по порядку—стеквершина справа—
не дошлив стекеcurпосчитан, #n — его место по возрастаниюnone: пустой потомок

stack = []; нужно 4-е наименьшее значение

01/41
сначала · назад · пуск · шаг
Скорость
1function kthSmallest(root, k):
2 stack = []
3 cur = root
4 while true:
5 while cur is not none:
6 stack.push(cur)
7 cur = cur.left
8 cur = stack.pop()
9 k = k - 1
10 if k == 0:
11 return cur.val
12 cur = cur.right
состояние
k
4
cur
–
stack
[]
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. В двоичном дереве поиска симметричный обход выдаёт значения от меньшего к большему, поэтому k-е извлечённое значение — k-е наименьшее.
  2. Со стеком обход можно оборвать посередине: как только k дошло до 0, возвращаемся, а узлы, которые ещё ждут или до которых не дошли, ничего не стоят.

Сложность

Время O(h + k), где h — высота дерева: один путь вниз до наименьшего значения, потом k извлечений. Память O(h): в стеке лежит один путь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.