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