Rearrange the tree in place so that every node's left pointer is None and the right pointers form a single chain that lists the nodes in preorder (node, then its left subtree, then its right subtree). Return the root. Do not create new nodes.
Examples
1
/ \
2 5
/ \ \
3 4 6
Input: root = build_tree([1, 2, 5, 3, 4, None, 6])
Output: tree_to_list(...) == [1, None, 2, None, 3, None, 4, None, 5, None, 6]
Input: root = build_tree([1, 2])
Output: [1, None, 2]
Constraints
0 <= number of nodes <= 1000
Goals
- Rewire pointers in place without losing the subtree that has not been processed yet
- Use reverse post-order so the previously finished node becomes the next right child