Почему это работает
- В прямом порядке правое поддерево узла идёт сразу за последним узлом его левого поддерева. Этот узел находим, если от node.left идти вправо, пока есть правый потомок.
- Если повесить туда правое поддерево, а левое перенести направо, прямой порядок сохраняется, а у node не остаётся левой ссылки.
- Потом node шагает вправо, и так обрабатываем каждый узел; всё выше node уже стало одним списком.
Сложность
Время O(n): node проходит каждый узел один раз, а last проходит каждую правую ссылку не больше одного раза. Память O(1): два указателя, без стека и рекурсии.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗