Java recursive solution


  • 10
    Q
    public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums == null || nums.length ==0){
                return null;
            }
            return getTreeNode(nums, 0, nums.length-1);
        }
        
        private TreeNode getTreeNode(int[] nums, int start, int end){
            if (start > end){
                return null;
            }
            int middle = start + (end-start)/2;
            TreeNode n = new TreeNode(nums[middle]);
            n.left = getTreeNode(nums, start, middle-1);
            n.right = getTreeNode(nums, middle+1, end);
            return n;
        }
    }

  • 0
    G

    Wow, this is virtually the same comparing to my C++ code.

    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            int n = nums.size();
            return toBSTInternal(nums, 0, n - 1);
        }
    private:
        TreeNode* toBSTInternal(vector<int>& nums, int l, int r) {
            if (l > r)
                return NULL;
            int mid = (l + r) >> 1;
            TreeNode *ans = new TreeNode(nums[mid]);
            ans -> left = toBSTInternal(nums, l, mid - 1);
            ans -> right = toBSTInternal(nums, mid + 1, r);
            return ans;
        }
    };

  • 1
    This post is deleted!

  • 0
    S

    Whats wrong with this code? Can anyone tell me . I had same approach in mind, but this doesnt work. I want to know the logic behind why its not working.

     public TreeNode sortedArrayToBST(int[] nums) {
            
            if(nums.length==0){
                return null;
            }
            TreeNode root=new TreeNode(nums[0]);
            sortHelper(nums,nums.length-1,0,root);
            return root;
            
            
        }
        
        public void sortHelper(int[] nums, int l, int h,TreeNode node){
            int m=(h+l)/2; 
            if(l>h){
                return;
            }          
             /*
               Even this fails. 
              TreeNode newNode=new TreeNode(nums[m]);
               node=newNode
           */     
            node.val=nums[m];
            sortHelper(nums,l,m-1,node.left);
            sortHelper(nums,m+1,h,node.right);
    
        } 
    

Log in to reply
 

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