After many insertions of already-sorted data, a search tree has degenerated into long chains. Return the root of a height-balanced search tree holding exactly the same values (at every node the two subtree heights differ by at most 1). Any balanced tree with the same values is accepted.
Examples
1
\ 2
2 / \
\ ==> 1 3
3 \
\ 4
4
Input: root = build_tree([1, None, 2, None, 3, None, 4])
Output (one valid answer): [2, 1, 3, None, None, None, 4]
Input: root = build_tree([3, 2, None, 1])
Output: [2, 1, 3]
Constraints
0 <= number of nodes <= 2000- All values are distinct integers
- O(n) time
Goals
- Extract the sorted values with an inorder traversal
- Rebuild a height-balanced tree from the middle outwards