96 & 95. Unique Binary Search Tree I & II

96. Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

My Solutions:

对于数组【1，2，3，4，5，6】来说，如果让4做root，结果就是[1,2,3]可以组成的树的数量乘以[5,6]可以组成树的数量。

如果数组为空，毫无疑问，只有一种BST，即空树，
Count[0] =1

如果数组仅有一个元素{1}，只有一种BST，单个节点
Count[1] = 1

如果数组有两个元素{1,2}， 那么有如下两种可能
1                       2
  \                    /
    2                1
Count[2] = Count[0] * Count[1]   (1为根的情况，左子树一定不存在，右子树可以有一个数字)
         + Count[1] * Count[0]  (2为根的情况，左子树可以有一个数字，右子树一定不存在)

再看一个三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2]  (1为根的情况，左子树一定不存在，右子树可以有两个数字)
         + Count[1]*Count[1]  (2为根的情况，左右子树都可以各有一个数字)
         + Count[2]*Count[0]  (3为根的情况，左子树可以有两个数字，右子树一定不存在)

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

95. Unique Binary Search Trees II

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

和#96类似，要求返回所有的树。

My Solutions:

public List<TreeNode> generateTrees(int n) {
    return generate(1, n);
}

public List<TreeNode> generate(int l, int r) {
    ArrayList<TreeNode> res = new ArrayList<>();
    if (l > r) {
        res.add(null);
        return res;
    }
    
    for (int i = l; i <= r; i++) {
        List<TreeNode> left = generate(l, i - 1);
        List<TreeNode> right = generate(i + 1, r);
        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);
                res.add(root);
            }
        }
    }
    return res;
}