Increasing Order Search Tree
Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
Example 1
5 1
/ \ \
3 6 2
/ \ \ \
2 4 8 -> 3
/ / \ \
1 7 9 4
\
5
\
6
\
7
\
8
\
9Input
root = [5,3,6,2,4,null,8,1,null,null,null,7,9]Output
[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]The nodes are rearranged in in-order sequence from 1 through 9, with each node having no left child and only a right child pointing to the next node.
Example 2
5 1
/ \ \
1 7 -> 5
\
7Input
root = [5,1,7]Output
[1,null,5,null,7]The in-order traversal is 1, 5, 7, so the resulting tree is a right-only chain in that order.
Constraints
- The number of nodes in the given tree will be in the range
[1, 100]. 0 <= Node.val <= 1000