10 line Java solution, Explanation given.


  • 3
    P

    The main point of the problem is to recognize how to build up the solution to the bigger problem( n ) using the
    solution to smaller problems( 0 , 1, .... n - 1 )

    The best way to understand would be draw out the possible combination for cases when n = 0, 1, 2, 3 and 4
    You should be able to see how to build the answer for higher values once you know the result for lower values of n. I got this relation... let's say that t(n) be the number of trees, then
    t(n) = Summation over i from 0 to n - 1 of ( t ( i ) * t ( n - 1 - i ) )

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

Log in to reply
 

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