My Accepted Java Solution


  • 112
    J

    Hi everyone, this is my accepted recursive Java solution. I get overflow problems at first because I didn't use mid - 1 and mid + 1 as the bound. Hope this helps :)

    public TreeNode sortedArrayToBST(int[] num) {
        if (num.length == 0) {
            return null;
        }
        TreeNode head = helper(num, 0, num.length - 1);
        return head;
    }
    
    public TreeNode helper(int[] num, int low, int high) {
        if (low > high) { // Done
            return null;
        }
        int mid = (low + high) / 2;
        TreeNode node = new TreeNode(num[mid]);
        node.left = helper(num, low, mid - 1);
        node.right = helper(num, mid + 1, high);
        return node;
    }

  • 1
    L

    My Java code which is almost same as the above: recursion and "sort of" binary search. The basic idea is always to pick the median as the node and repeat the process for left and right subtrees.

    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0) return null;
        TreeNode root = new TreeNode(0);
        insertNode(root,num,0,num.length-1);
        return root;
    }
    
    public void insertNode(TreeNode root, int[] num, int s, int e){
    	if (s==e){
    		root.val = num[s];
    		return;
    	}
    	int mid = (s+e)%2 == 0 ? (s+e)/2 : (s+e)/2+1;
    	root.val = num[mid];
    	if (mid-s >= 1){
    		root.left = new TreeNode(0);
    		insertNode(root.left,num,s,mid-1);
    	}
    	
    	if (e-mid >=1){
    		root.right = new TreeNode(0);
    		insertNode(root.right,num,mid+1,e);
    	}
    	return;
    }

  • 0
    C

    I thought (-1)/2 was illegal......I am wrong


  • 1
    Y

    "if (num.length == 0) {
    return null;
    }"

    this part can be removed, which makes the code even shorter :D


  • 13
    H

    My code with similar ideas. Comments are welcome.

    public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length-1);
    }
    public TreeNode sortedArrayToBST(int[] nums, int lo, int hi){
        if(lo > hi)
            return null;
        int mid = (hi-lo)/2+lo;
        TreeNode root = new TreeNode(nums[mid]);
        root.left =  sortedArrayToBST(nums, lo, mid-1);
        root.right =  sortedArrayToBST(nums, mid+1, hi);
        return root;
    }
    

    }


  • 19

    int mid = low + (high-low)/2; // avoids integer overflow


  • 0
    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            return help(nums, 0, nums.size()-1);
        }
        
        TreeNode* help(vector<int> &nums, int start, int end){
            int _size=end-start;
            if(_size<0)    return NULL;
            if(_size==0)    return new TreeNode(nums[start]);
            int mid=(start+end)/2;
            TreeNode* root=new TreeNode(nums[mid]);
            root->left=help(nums, start, mid-1);
            root->right=help(nums, mid+1, end);
        }
    };

  • 0
    V

    Shorter..

    public TreeNode sortedArrayToBST(int[] nums) {
        return createTree(nums, 0, nums.length - 1);
    }
    
    public TreeNode createTree(int[] nums, int start, int end){
        if(start > end) return null;
        int middle = (start + end) / 2;
        TreeNode node = new TreeNode(nums[middle]);
        node.left = createTree(nums, start, middle-1);
        node.right = createTree(nums, middle+1, end);
        return node;
    }

  • 0
    W

    Shorter...

    public TreeNode sortedArrayToBST(int[] nums) {
            if (nums == null || nums.length == 0) return null;
            int len = nums.length;
            TreeNode root  = new TreeNode(nums[len/2]);
            root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, len/2));
            root.right = sortedArrayToBST(Arrays.copyOfRange(nums, len/2 + 1, len));
            return root;
        }
    

  • 0
    A

    @jiaming2 What is the running time for this solution?


  • 0
    T

    @WTYJack I have the exactly same answer as yours, just wondering is there anything bad using copyOfRange method so that few people uses it.


  • 0
    Y

    could anybody tell why this code doesn't work?

        public TreeNode sortedArrayToBST(int[] nums) {
            if(nums.length == 0) return null;
            int mid = (nums.length-1)/2;
            TreeNode root = new TreeNode(nums[mid]);
            recursive(nums, 0, mid-1, root.left);
            recursive(nums, mid+1, nums.length-1, root.right);
            return root;
        }
        
        public void recursive(int [] nums, int start, int end, TreeNode root){
            if(start > end){
                root = null;
                return;
            };
            int mid = (end + start)/2;
            root = new TreeNode(nums[mid]);
            recursive(nums, start, mid-1, root.left);
            recursive(nums, mid+1, end, root.right);
        }
    }```

  • 0
    P

    @acheiver I had the same question actually! I was thinking its either O(n) or O(nlgn)... I think it may be O(n). My thought is as follows - that recursive function is 'run' once for every element in the list.

    Let me know your thoughts


  • 0

    @yiluxiangnan123 I think you're not setting the left and right subtrees to the root. root.left = recursive(... and root.right = recursive(...


  • 3
    W

    @tongzongjian @WTYJack This answer is shorter and works as intended, but has a worse performance compared to that of the original solution. Since Arrays.copyOfRange() takes O(N) time, the solution ends up taking O(NLogN) time, whereas the solution in the original post takes O(N) time.

    Recurrence relation of @WTYJack's solution: T(n) = 2T(n/2) + O(n) = O(nlog n)
    Recurrence relation of original solution: T(n) = 2*T(n/2) + O(1) = O(n).


  • 0
    S

    same code, though I add a param

    public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return findNextInsert(nums, 0, nums.length - 1, null);
        }
    
        private TreeNode findNextInsert(int[] nums, int left, int right, TreeNode node) {
            if(left > right) return null;
            int mid = (left+right) / 2;
            node = new TreeNode(nums[mid]);
            node.left = findNextInsert(nums, left, mid-1, node.left);
            node.right = findNextInsert(nums, mid+1, right, node.right);
            return node;
        }
    }
    

  • 0

    @jaqenhgar yeah you are right.


  • 0
    B

    @acheiver @preethikandhalu
    I think the run time of the above algorithm is O(n) since we access all the elements of the array once. The space complexity is also O(n) since we use recursion which uses an implicit stack.

    Please let me know if you think otherwise. Thank you!


Log in to reply
 

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