16ms - C++ recursive approach using binary search algorithm


  • 0
    class Solution {
    public:
        TreeNode *head;
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            if(nums.empty()) return head;
            int l = 0, r = nums.size()-1;
            int mid = (l+r+1)/2;
            head = new TreeNode(nums[mid]);
            insert(head, l, mid-1, nums);
            insert(head, mid+1, r, nums);
            return head;
        }
        
        void insert(TreeNode* parent, int l, int r, vector<int>&nums){
            if(l>r) return;
            int mid = (l+r+1)/2; TreeNode *tmp;
            if(nums[mid] < parent->val) {
                parent->left = new TreeNode(nums[mid]); tmp = parent->left;
            }
            if(nums[mid] >= parent->val) {
                parent->right = new TreeNode(nums[mid]); tmp = parent->right;
            }
            if(l==r)return;
            insert(tmp, l, mid-1, nums);
            insert(tmp, mid+1, r, nums);
        }
        
    };

  • 0
    A simpler version:
    
    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            if(nums.empty()) return NULL;
            return insert(0, nums.size()-1, nums);
        }
        
        TreeNode* insert(int l, int r, vector<int>&nums){
            if(l>r) return NULL;
            int mid = (l+r+1)/2; TreeNode* root = new TreeNode(nums[mid]);
            root->left = insert(l, mid-1, nums); 
            root->right = insert(mid+1, r, nums);
            return root;
        }
        
    };

Log in to reply
 

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