506. Balanced From Sorted
A museum receives a list of exhibit numbers already sorted in strictly increasing order and wants to file them in a binary search tree that is height-balanced: for every node, the heights of its left and right subtrees differ by at most one.
Given nums, build any such tree that contains exactly the numbers of nums, each once, and return its root. Several different trees can be valid, and any of them is accepted as long as an in-order reading of the tree gives nums back and the balance condition holds at every node.
Example 1
- Input:
- nums = [2,4,6,8,10,12]
- Output:
- [6,2,10,null,4,8,12]
- Explanation:
Any search tree holding these six keys whose subtrees differ in height by at most one is accepted, for example a root of 6 with a balanced left and right part.
Example 2
- Input:
- nums = [1,3]
- Output:
- [1,null,3]
- Explanation:
Either 1 as root with 3 as its right child, or 3 as root with 1 as its left child, is balanced.
Constraints
1 ≤ nums.length ≤ 104
-109 ≤ nums[i] ≤ 109
nums is sorted in strictly increasing order.
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(log n)