108. Convert Sorted Array to Binary Search Tree

惭愧啊，虽然二刷和一刷思路运行时间都一样，但是二刷代码居然比一刷还繁琐。

二刷傻了，居然分情况讨论有1,2,3个的时候。。其实直接来就行。

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) 
    {
        if(nums.length == 0) return null;

        TreeNode res = helper(nums,0,nums.length-1);
        
        
        return res;
    }
    
    public TreeNode helper(int[] nums,int L, int R)
    {
        if(L == R) return new TreeNode(nums[L]);
        else if(L > R) return null;
        else
        {
            int M = L + (R - L)/2;
            TreeNode res = new TreeNode(nums[M]);
            res.left = helper(nums,L,M-1);
            res.right = helper(nums,M+1,R);
            
            return res;
        }
        
        
    }
    
    
}

---

---

三刷。

按divide&conquer里的divide分，最后和一起就行了。

递归，每次选中点M，left subtree (L~(m-1)) right subtree ((m+1) ~ R)

Time : O(lgN)
Space: O(lgN) memory stack.

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return helper(nums, 0, nums.length - 1);
    }
    
    public TreeNode helper(int[] nums, int l, int r) {
        if (l == r) {
            return new TreeNode(nums[l]);
        } else if (l > r) {
            return null;
        } else {
            int m = l + (r - l)/2;
            TreeNode res = new TreeNode(nums[m]);
            res.left = helper(nums, l, m - 1);
            res.right = helper(nums, m + 1, r);
            return res;
        }
    }
}