522. Rebalance the Search Tree
A library keeps its card catalogue in a binary search tree of distinct integer keys, but years of adding cards in order have stretched it into a long, lopsided chain. Rebuild it.
Given the tree root, return the root of a new binary search tree that holds exactly the same keys and is height-balanced: at every node, the heights of the left and right subtrees differ by at most 1. Many balanced trees can exist for the same keys, and any of them is accepted. For an empty tree return an empty tree.
Example 1
- Input:
- root = [3,null,7,null,12,null,18]
- Output:
- [7,3,12,null,null,null,18]
- Explanation:
The input is a right-leaning chain; making 7 the root with 3 on its left and 12 (with 18 below it) on its right gives a balanced tree with the same keys.
Example 2
- Input:
- root = [20,10,30,5,null,25,null,2]
- Output:
- [10,2,25,null,5,20,30]
- Explanation:
The six keys 2, 5, 10, 20, 25, 30 are re-hung with 10 as root, 2 (with child 5) on the left and 25 (with children 20 and 30) on the right; any balanced search tree with the same keys is accepted.
Constraints
0 ≤ number of nodes ≤ 104
-105 ≤ node value ≤ 105
All keys are distinct and the input is a valid binary search tree
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)