What's the time complexity of my solution? it is accepted.


  • 0
    Y

    class Solution
    {
    public:

    int calculateSubTree(int start, int end)
    {
        if (start == end) return 1;
        
        int sum = 0;
        for (int i = start; i<=end ;i++)
        {
            sum += numTreesInternal(start, i, end);
        }
        
        return sum;
    }
    
    int numTreesInternal(int left, int middle, int right)
    {
        int sum = 1;
        if (middle > left)
        {
            sum *=  calculateSubTree(left, middle-1);
        }
        
        if (right > middle)
        {
            sum *=  calculateSubTree(middle+1, right);   
        }
        
        return sum;
    }
    
    int numTrees(int n)
    {
        return calculateSubTree(1, n);
    }
    

    };


Log in to reply
 

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