Почему это работает
- В стеке лежат ровно те узлы, которые симметричный обход ещё должен выдать: каждый ждёт под узлами своего левого поддерева, поэтому наверху всегда наименьшее из ещё не выданных.
- Когда next() достал узел, следующие значения — в его правом поддереве, наименьшие по его левой стороне; pushLeft кладёт их наверх, поверх предков узла, которые идут позже.
- За все вызовы каждый узел кладём в стек и достаём один раз, поэтому next() в среднем O(1), даже если один вызов кладёт целый путь.
Сложность
Время в среднем O(1) на вызов: n добавлений и n извлечений делятся на n вызовов next(); hasNext() — O(1). Память O(h): в стеке не больше одного пути от корня.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗