dsa · easy
Sorted Array to Height-Balanced Search Tree
nums is a strictly increasing sorted array. Build a **height-balanced binary search tree** that stores each entry of nums exactly once.
Arguments
nums— strictly increasing sorted integers to store in the tree
A search tree here means every value in a left subtree is smaller than the node and every value in a right subtree is larger. Height-balanced means that at every node the two child subtree heights (empty height 0, a leaf height 1) differ by at most one.
Several trees can satisfy that. Return the unique tree obtained by always taking the **middle** value of each remaining contiguous slice as the node. When a slice has even length, take the **left** of the two central values.
Encode the tree as [val, left, right] or None.
Example
nums = [-10, -3, 0, 5, 9] has five entries. The middle (index 2) is 0, so 0 is the root.
Left slice [-10, -3]: left-middle is -10, with right child -3.
Right slice [5, 9]: left-middle is 5, with right child 9.
The tree is [0, [-10, None, [-3, None, None]], [5, None, [9, None, None]]].
Constraints
1 <= nums.length <= 2000 nums is sorted in strictly increasing ascending order -10^4 <= nums[i] <= 10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [-10, -3, 0, 5, 9] Expected: [0,[-10,null,[-3,null,null]],[5,null,[9,null,null]]]
Example 2
Input: [1, 3] Expected: [1,null,[3,null,null]]