Simple recursive solution share in C++ (AC in 10ms)


  • 0
    J
    class Solution {
    public:
        int numTrees(int n) {
            // Base cases
        	if (n == 0 || n == 1) return 1;
        	// Do recursion
        	int treeCount = 0;
        	for (int i = 0; i != n; ++i)
        		treeCount += numTrees(i) * numTrees(n - 1 - i);
        	return treeCount;
        }
    };
    

    Also easy to understand !


  • 0
    E
    // my java version, not slower than c++;
    public class Solution {
        public int numTrees(int n) {
            if (n == 1 || n == 0) {
                return 1;
            } else {
                int count = 0;
                int remains = n - 1;
                while (remains >= 0) {
                    count += (numTrees(remains) * numTrees(n - 1 - remains));
                    remains--;
                }
                return count;
            }
        }
    }

  • 0
    L

    why is my DP solution taking 28 ms and your recursive solution taking 10 ms !!!

    class Solution {
    public:
        int numTrees(int n) {
           if(n==0)
            return 0;
            
           vector<int> arr;
           arr.push_back(1);
           arr.push_back(1);
           arr.push_back(2);
           int temp=0;
           for(int i=3 ; i<=n ; i++)
            {
                for(int j=1 ; j<=i/2 ; j++)
                  temp+=arr[j-1]*arr[i-j];
                  
                 temp=2*temp;
                 if(i%2!=0)
                   temp+=arr[i/2]*arr[i-i/2-1];
                 arr[i]=temp;
                 temp=0;
            }
            return arr[n];
        }
    };

  • 0
    J

    Why the code can be AC? It will take an index out of range, isn't it?


  • 0
    H

    I only changed the following and it AC with 4 ms;
    {{
    vector<int> arr(n+1);
    arr[0]=1;
    arr[1]=1;
    arr[2]=2;}}


  • 0
    L

    thanks a lot,i get the difference .Its easier to fill value in already allocated memory than allocating it every time and filling it.


Log in to reply
 

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