475. Flatten to a Spine
A librarian has a branching shelf plan stored as a binary tree and wants to turn it into one straight shelf without creating any new shelves. Reorder the existing nodes in place so that every node's left pointer becomes null and its right pointer points to the node that comes next in preorder, that is the order in which a traversal visits a node, then its whole left subtree, then its whole right subtree.
Modify the tree rooted at root in place; the method returns nothing. After the call the nodes must form a single right-leaning chain that starts at root, with the same node objects in preorder sequence. If root is empty, do nothing.
Example 1
- Input:
- root = [5,2,8,1,3,null,9]
- Output:
- [5,null,2,null,1,null,3,null,8,null,9]
- Explanation:
The preorder sequence 5,2,1,3,8,9 becomes a right-leaning chain with no left children, written level by level as [5,null,2,null,1,null,3,null,8,null,9].
Example 2
- Input:
- root = [6,null,4,7]
- Output:
- [6,null,4,null,7]
- Explanation:
The preorder sequence 6,4,7 becomes a right-leaning chain with no left children, written level by level as [6,null,4,null,7].
Example 3
- Input:
- root = [3,1,null,null,2]
- Output:
- [3,null,1,null,2]
- Explanation:
The preorder sequence 3,1,2 becomes a right-leaning chain with no left children, written level by level as [3,null,1,null,2].
Constraints
0 ≤ number of nodes ≤ 2000
-1000 ≤ Node.val ≤ 1000
Rewire the existing nodes; do not allocate a new tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
rootafter your method returns. - Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)