You get an array nums whose values are in strictly increasing order. Build a binary search tree that holds exactly these values, one node each, and return its root. In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.
The tree must also be height-balanced: at every node, the heights of the left and right subtrees differ by at most 1.
Usually more than one tree fits. Any height-balanced binary search tree over nums is accepted; the outputs below show one of them.
0 sits in the middle of the array, so it takes the root, with two values on each side. Each side then picks a root of its own the same way. [0,-2,11,-7,null,5] would be accepted too.
With two values, either can be the root: [9,4] is just as balanced and is accepted as well.
Reading this tree in order (left subtree, node, right subtree) gives back nums, and no two sibling subtrees differ in height by more than one level.
Constraints
1 <= nums.length <= 10⁴-10⁴ <= nums[i] <= 10⁴nums is sorted in strictly increasing order.The root of a balanced tree should split the values as evenly as possible: pick the middle of the array. Everything to its left goes in the left subtree and everything to its right in the right subtree, which keeps the search-tree order for free.