Convert Sorted Array to BST
Easy · tree dfs
You are given an array nums of distinct integers sorted in increasing order. Build a height-balanced binary search tree that holds exactly these values, and return its root.
Many trees would qualify, so the shape is fixed to make the answer unique:
- The root is the middle element of the array. If the array has an even length there are two middle elements; use the left one (the one with the smaller index).
- The part of the array to the left of the middle builds the left subtree, and the part to the right builds the right subtree. Each part is built by the same rule.
- An empty part gives an empty subtree.
If nums is empty, return the empty tree.
Examples
Example 1
Input: nums = [-10, -3, 0, 5, 9]
Output: [0, -10, 5, null, -3, null, 9]
The middle of five values is 0, so it is the root. [-10, -3] builds the left subtree and [5, 9] the right one.
Example 2
Input: nums = [1, 3]
Output: [1, null, 3]
Two values have two middles, 1 and 3. The left one, 1, becomes the root, and 3 is its right child.
Example 3
Input: nums = [4]
Output: [4]
Constraints
- 0 <= len(nums) <= 1000
- -10^4 <= nums[i] <= 10^4
- nums is sorted in strictly increasing order.