Why it works
- In pre-order, a node's right subtree comes right after the last node of its left subtree. That node is found by going right from node.left until there is no right child.
- Hanging the right subtree there and moving the left subtree to the right keeps the pre-order and leaves node with no left link.
- node then steps right, so every node gets the same treatment, and the parts above node are already one list.
Complexity
Time O(n): node visits each node once, and last walks each right link at most once more. Memory O(1): two pointers, no stack, no recursion.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗