Given the root of a binary tree, flatten it in place into a "linked list" made of the same nodes. Each node's right pointer should point to the next node and every left pointer should be null. The order of the nodes must be the preorder traversal of the original tree. The function returns nothing.
- 0 <= number of nodes <= 2000
- -100 <= Node.val <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simple way is to record the preorder sequence in a list and relink the nodes, which uses O(n) extra space. To do it in O(1) space, look at one node at a time. In preorder, the last node visited in its left subtree is the rightmost node of that subtree, and the old right subtree comes right after it. So we attach the right subtree to that rightmost node, move the whole left subtree into the right pointer, and clear left. Repeating this while walking down the right pointers flattens the whole tree.
Algorithm
- Set
cur = root. - While
curis not null: ifcur.leftexists, findpre, the rightmost node incur.left. - Set
pre.right = cur.right, thencur.right = cur.leftandcur.left = null. - Move
cur = cur.rightand repeat.
O(n), each edge is walked at most twiceSpace: O(1)left = null is the most common bug: the output still looks right when printed through right pointers, but the judge sees a tree that is not a chain.class Solution: def flatten(self, root: Optional[TreeNode]) -> None: cur = root while cur: if cur.left: # Rightmost node of the left subtree pre = cur.left while pre.right: pre = pre.right pre.right = cur.right # old right subtree goes after the left subtree cur.right = cur.left cur.left = None cur = cur.right