Accepted C++ recursive solution within a single method


  • 33
    P

    Recursively call the sortedArrayToBST() method providing new vector for each call to construct left and right children:

    class Solution {
    public:
        TreeNode *sortedArrayToBST(vector<int> &num) {
            if(num.size() == 0) return NULL;
            if(num.size() == 1)
            {
                return new TreeNode(num[0]);
            }
            
            int middle = num.size()/2;
            TreeNode* root = new TreeNode(num[middle]);
            
            vector<int> leftInts(num.begin(), num.begin()+middle);
            vector<int> rightInts(num.begin()+middle+1, num.end());
            
            root->left = sortedArrayToBST(leftInts);
            root->right = sortedArrayToBST(rightInts);
            
            return root;
        }
    };

  • 5
    R
    if(num.size() == 1)
    {
        return new TreeNode(num[0]);
    }
    

    The above part is redundant. Nevertheless, your code is still concise and inspiring.


  • 1
    S

    Why don't you have a helper function and pass lo,hi instead of passing new vectors in each and every call?


  • 3

    A more efficient and concise implementation

     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
    L

    @sudeep3
    Are you asking this because you don't know or because you want him to use the helper method approach ?


  • 0
    S

    Very fun alternative but this uses the copy constructor which kills performance for arrays of any large length.


  • 0
    S

    How come your help function does not always return a value?
    your return value only exist in if statement. the leaf node will return for sure, but the parent node may not?
    But anyway, if I add a return at the end like "return root;", it does not make difference


  • 0
    N

    I think because it is a recursive solution, keep new new objects might incur more memory consumption than just using begin and end index of the array. In the worst case, the memory will run out.


  • 1
    A

    Time complexity of your algorithm is O(nlogn) because of the copy. Following is the amount of the copy. And it also requires O(nlogn) space. I think this is not a considerable solution because
    the simple recursion with the indexes runs in O(n) time and O(logn) space.

    # When n = 16
    L1               8 8
    L2             4 4 4 4
    L3         2 2 2 2 2 2 2 2
    L4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    ```

  • 0
    Z

    The special case doesn't need
    if(num.size() == 1)
    {
    return new TreeNode(num[0]);
    }


Log in to reply
 

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