16 ms C++ solution simple and easy :)


  • 0
    N
    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            int n=nums.size();
            TreeNode *root, *temp;
                if(n==0) return NULL;
                root = new TreeNode(nums[n/2]);
                //root->val=nums[n/2];
                if(n==2){
                    temp = new TreeNode(nums[0]);
                    //temp->val=nums[0];
                    root->left=temp;
                    root->right=NULL;
                }
                if(n>2){
                root->left=MakeBST(nums,0,n/2-1);
                root->right=MakeBST(nums,n/2+1,n-1);}
                return root;
        }
    private:
        TreeNode* MakeBST(vector<int>& a,int lo,int hi){
            TreeNode *p=NULL;
            if(lo==hi) {
               p = new TreeNode(a[lo]);
            // p->val=a[lo];
             return p;
            }
            if(lo<hi)
            {
                int mid=(lo+hi+1)/2;
                 p = new TreeNode(a[mid]);
                 //p->val=a[mid];
                 p->left=MakeBST(a,lo,mid-1);
                 p->right=MakeBST(a,mid+1,hi);
            }
            else return NULL;
        }
    }

  • 0
    L

    Make it simple! This java code runs in 1ms

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

  • 0
    N

    It really reduced running time, Thanks for your suggestion :)


Log in to reply
 

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