[Leetcode] Unique Binary Search Trees II

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

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

使用递归来寻找左右子树的所有可能节点，然后组合到一起之后返回。

    public List<TreeNode> generateTrees(int n) {
        return generateTrees(n, 1);
    }
    
    public List<TreeNode> generateTrees(int n, int beg) {
        if(n == 0) {
            List<TreeNode> result = new ArrayList<TreeNode>();
            result.add(null); // null should be add explicitly
            return result;
        }
        else {
            List<TreeNode> result = new ArrayList<TreeNode>();
            for(int i = beg; i < beg+n; i++) {
                List<TreeNode> left = generateTrees(i-beg, beg); // pay attention to the return type
                List<TreeNode> right = generateTrees(n-i+beg-1, i+1);
                for(TreeNode node1 : left) {
                    for(TreeNode node2 : right) {
                        TreeNode root = new TreeNode(i);
                        root.left = node1;
                        root.right = node2;
                        result.add(root);
                    }
                }
            }
            return result;
        }
    }