1ms, O(n) Recursive Java solution, using O(logn) space for recursive stack.

  • 0
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     //O(n) time Recursive Java solution with O(logn) space for recursive stack. 
    public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            TreeNode r=null;
            if(nums==null) return r;
            int l = nums.length;
            if(l==0) return r;
            return toBST(nums,0,l-1);
        TreeNode toBST(int[]nums, int min, int max){
            if(min==max)    return new TreeNode(nums[min]);
            int mid=(max-min+1)/2 + min;
            TreeNode r = new TreeNode(nums[mid]);
            if(mid-1>=min) r.left = toBST(nums, min, mid-1);
            if(mid+1<=max) r.right = toBST(nums, mid+1, max);
            return r;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.