How I can speed up my solution?


  • 0
    R

    Here is the code, it is timelimit, I wonder how to make it faster?

    class Solution {
    public:
        int numTrees(int n) {
            return numTrees(1,n, 0, n);
        }
    private:
        int numTrees(int minV, int maxV, int num_nodes, int n) {
            if(minV==maxV) return 1;
    	    if(minV > maxV) return 0;
            int sum=0;
            for(int i=minV; i<=maxV; ++i){
                int left  = numTrees(minV, i-1, num_nodes+1, n); //try with the left
                int right = numTrees(i+1, maxV, num_nodes+1, n); //try with the right 
                if(left==0 || right ==0)
                    sum+=max(left,right);
                else
                    sum+=(left*right);
            }
            return sum;
        }
        
    };

  • 0
    R

    Hi rabeeh,

    You should look into Dynamic programming, and also see that the answer depends on the size of the subtree, not on where this subtree is.

    The accepted solution runs in 0 ms.

    Hope it helps.


Log in to reply
 

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