Convert Sorted Array to Binary Search Tree

Given an integer array nums sorted in ascending order, convert it to a height-balanced binary search tree and return its root. A height-balanced tree is one where, for every node, the depths of its two subtrees differ by no more than one.

There may be more than one valid answer for a given input; the grader accepts the specific balanced tree produced by always making the middle element (rounding down on ties) the subtree root, exactly as shown in the example below.

Input / output

• Input: nums: int[]
• Output: TreeNode (JSON test fixture is a LeetCode-style level-order array, e.g. [0,-3,9,-10,null,5], with null for a missing child)

Constraints

• 0 <= nums.length <= 10,000
• -100,000 <= nums[i] <= 100,000
• nums is sorted in strictly increasing order.

Follow-up

Can you build the tree in O(n) total time by walking the array with an index cursor instead of re-slicing it at every recursive call?