Binary Search Tree Iterator

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

Нужно сделать итератор по двоичному дереву поиска. Он создаётся по корню; next() возвращает следующее значение по возрастанию, а hasNext() говорит, остались ли ещё значения. Обе операции — в среднем за O(1) по времени и O(h) по памяти, где h — высота дерева. Наше дерево: 12 с потомками 5 и 17; у 5 правый потомок 9; у 17 левый потомок 14. Наши вызовы: BSTIterator(root), next(), next(), next(), hasNext(), next(), next(), hasNext() — они вернут 5, 9, 12, true, 14, 17, false.

173 Binary Search Tree IteratorРазбор · 1×

Пример: BSTIterator(root), next(), next(), next(), hasNext(), next(), next(), hasNext() на двоичном дереве поиска: симметричный обход со стеком, по одному значению за вызов.

nonenonenonenonenonenone12517914next()вернул—стеквершина справа—
ещё не дошлив стекеnodeснят со стека, next() вернёт еговыдан next(), #n — его очередьnone: пустой потомок

BSTIterator(root), root = 12

01/48
сначала · назад · пуск · шаг
Скорость
1class BSTIterator:
2 function init(root):
3 stack = []
4 pushLeft(root)
5 function next():
6 node = stack.pop()
7 pushLeft(node.right)
8 return node.val
9 function hasNext():
10 return stack is not empty
11 function pushLeft(node):
12 while node is not none:
13 stack.push(node)
14 node = node.left
состояние
node
–
stack
[]
историянажмите шаг, чтобы вернуться

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

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

  1. В стеке лежат ровно те узлы, которые симметричный обход ещё должен выдать: каждый ждёт под узлами своего левого поддерева, поэтому наверху всегда наименьшее из ещё не выданных.
  2. Когда next() достал узел, следующие значения — в его правом поддереве, наименьшие по его левой стороне; pushLeft кладёт их наверх, поверх предков узла, которые идут позже.
  3. За все вызовы каждый узел кладём в стек и достаём один раз, поэтому next() в среднем O(1), даже если один вызов кладёт целый путь.

Сложность

Время в среднем O(1) на вызов: n добавлений и n извлечений делятся на n вызовов next(); hasNext() — O(1). Память O(h): в стеке не больше одного пути от корня.

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

Решить на LeetCode ↗

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