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