Unique Binary Search Trees I && II

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

比较巧妙的思路，假设我们有n个点，我们取i作为root，那左子树就是1到i - 1个点组成的情况，右子树就是i + 1到n组成的情况。把每个点作为root的情况进行累加，所以当我们知道1，2...n个点的组成树的种类，我们也能知道n + 1个点组成树的种类。

public class Solution {
    //Time: O(n^2)  Space: O(n)
    public int numTrees(int n) {
        int[] map = new int[n + 1];
        map[0] = map[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                map[i] += map[j - 1] * map[i - j];
            }
        }
        return map[n];
    }
}

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
  return generate(1, n);
    }
    
    private ArrayList<TreeNode> generate(int start, int end) {
        ArrayList<TreeNode> bst = new ArrayList<TreeNode>();
        if (start > end) {
            bst.add(null);
            return bst;
        }
        
        for (int i = start; i <= end; i++) {
            ArrayList<TreeNode> left = generate(start, i - 1);
            ArrayList<TreeNode> right = generate(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode root = new TreeNode(i);
                    root.left = left.get(j);
                    root.right = right.get(k);
                    bst.add(root);
                }
            }
        }
        return bst;
    }
}