Easy solution using recursive formula


  • 1
    Y

    f(0)=0

    f(n)=sum(f(i)*f(n-1-i)),i=0..n-1.

    class Solution {
    public:
        int numTrees(int n) {
            int* nums=new int[n+1];
    		for(int i=0;i<n+1;i++)
    			nums[i]=0;
    		nums[0]=1;
    		for(int i=1;i<n+1;i++)
    			for(int j=0;j<i;j++)
    				nums[i]+=nums[j]*nums[i-1-j];
    		return nums[n];
        }
    };

Log in to reply
 

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