Given the root of a binary search tree, rearrange the tree so that it becomes an increasing order search tree in which every node has only a right child. Pattern focus: BST Iterator Thinking. This problem turns the inorder sequence into a right-skewed tree, which is effectively a tree built from the iterator order.
root = binary tree root
root of the increasing-order right-skewed tree
Example 1:
Input:
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]
Explanation:
The tree is rewritten as a right-skewed chain in sorted order.
Example 2:
Input:
root = [2,1,3]
Output:
[1,null,2,null,3]
Explanation:
The output tree contains the same values in ascending order only on the right links.