Recursive is not suitable, but still a good definition.


  • 0

    Recursive is not suitable about this question, but more a definition of the answer, numTrees(N).

    int numTrees(int n) {
        if(n<1) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 5;
    
        // n can be at rightest position or the root
        int ans=numTrees(n-1)*2;
    
        for(int i=1; i<=n-2; i++)
        // n's subtree is i largest number.
            ans+=numTrees(i)*numTrees(n-1-i);
        return ans;
    }

Log in to reply
 

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