Pure Recursive solution Accepted [JAVA]


#1
public class Solution {
    public int numTrees(int A) {
        if(A==0)return 0;
        int res = 0;
        for(int i=1;i<=A;i++){
            int left = numTrees(1, i-1);//numbers of left subtree
            int right = numTrees(i+1, A);//numbers of right subtrees
            res+= (left==0?1:left)*(right==0?1:right);//total tree when [i] is root;
        }
        return res;
    }
    public int numTrees(int left, int right){
        if(left>right)return 0;
        if(left==right)return 1;//base case
        int res = 0;
        for(int i=left;i<right+1;i++){
            int numLeft = numTrees(left, i-1);//total number of subtree from [left...i-1]
            int numRight = numTrees(i+1, right);//total number of subtree from [i+1...right]
            res+= (numLeft==0?1:numLeft)*(numRight==0?1:numRight);//total tree [i] as root
        }
        return res;
    }
}