Approach #1 TailRecursive Solution [Accepted]
Algorithm
The key idea is to use two pointer
and recursive method to help construct the BST.
We init the root
node and then set its left and right subtree with corresponding indices.
Because of recursive calls on the helper()
method, we will have a BST at the end.
Java
public class Solution {
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null  nums.length == 0) return null;
return helper(nums, 0, nums.length  1);
}
private TreeNode helper(int[] nums, int left, int right) {
if (left > right) return null;
int mid = (left + right) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = helper(nums, left, mid  1);
node.right = helper(nums, mid + 1, right);
return node;
}
}
Complexity Analysis

Time complexity : $$O(n)$$, where n is the length of given array.

Space complexity : $$O(n)$$. The recursive function is called
n
times in the method stack.