Unique Binary Search Tree I and II

A very interesting problem. At first glance, I had no idea how to approach it. Thanks to Stackoverflow (again), for helping me solve the problem.

According to Binary Search Tree's definition, in order for node i to be the root, it's left subtree can only be generated from node 0 to i - 1, and it's right subtree can only be generated from i + 1 to n.

So, Tree[n] = Tree[0] * Tree[n - 1] + Tree[1] * Tree[n - 2] + ... + Tree[i] * Tree[n - i - 1] + ... + Tree[n - 1] * Tree[0]

public class UniqueBST {
    public int numTrees(int n) {
        if (n < 0)
            return 0;
        if (n == 0 || n == 1)
            return 1;
        int[] Tree = new int[n + 1];
        Tree[0] = 1;
        Tree[1] = 1;
        
        for (int i = 2; i <= n; i++)
        {

            //j represents the left subtree
            for (int j = 0; j < i; j++)
                Tree[i] += Tree[j] * Tree[i - j - 1];
        }
        return Tree[n];
        
    }
}

The second problem is derived from the same idea. The only difference is, now we need to use recursion to generate every left and right subtree.

public class Solution {
    public ArrayList generateTrees(int n) {
        return generateTreeHelper(1, n);
    }
    private ArrayList generateTreeHelper(int start, int end)
    {
        ArrayList rst = new ArrayList();
        //reach to the leaf
        if (start > end)
        {
            rst.add(null);
            return rst;
        }
        for (int i = start; i <= end; i++)
        {
            ArrayList left = generateTreeHelper(start, i - 1);
            ArrayList right = generateTreeHelper(i + 1, end);
            for (TreeNode l : left)
            {
                for (TreeNode r : right)
                {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    rst.add(root);
                }
            }
            
        }
        return rst;
    }
}