Почему это работает
- В стеке лежит путь от корня до cur, как вызовы в рекурсивном обходе. Узел уходит из него, только когда оба его поддерева уже в out.
- Узел с правым потомком оказывается на вершине стека дважды: до своего правого поддерева и после него. last — узел, который только что попал в out, поэтому если node.right — это last, мы возвращаемся.
- Без last во второй раз мы снова ушли бы вправо и зациклились.
Сложность
Время O(n): каждый узел один раз кладём в стек и один раз снимаем, а на вершине видим не больше двух раз. Память O(h), где h — высота дерева: в стеке лежит один путь от корня вниз.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗