[LeetCode每日一题]95. Unique Binary Search Trees II

题目如下：

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

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

95. Unique Binary Search Trees II
给定一个自然数n，找出所有由1-n组成的不同的二叉搜索树。这是这个系列的第二道题，这道题同样可以用动态规划解决。dp[i]存储由1~i组成的所有二叉搜索树，怎样求这样的二叉搜索树呢？首先1~i都可以作为BST的根节点，假设以r为根，则r的左子树为1~(r-1)组成的BST；右子树为(r+1)~i组成的BST，该右子树可由1~(i-r)组成的BST每个节点均增加r得来。由此计算，可得dp[n]是原问题的解。
实现代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        List<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        dp[0].add(null);
        dp[1] = new ArrayList<>();
        TreeNode root = new TreeNode(1);
        dp[1].add(root);
        for (int len = 2; len <= n; len++) {
            dp[len] = new ArrayList<>();
            for (int r = 1; r <= len; r++) {
                for (TreeNode left : dp[r - 1]) {
                    int remain = len - r;
                    for (TreeNode right : dp[remain]) {
                        TreeNode node = new TreeNode(r);
                        node.left = left;
                        node.right = doOffset(right, r);
                        dp[len].add(node);
                    }
                }
            }
        }
        return dp[n];
    }

    private TreeNode doOffset(TreeNode root, int offset) {
        if (root == null) {
            return null;
        }
        TreeNode node = new TreeNode(root.val + offset);
        node.left = doOffset(root.left, offset);
        node.right = doOffset(root.right, offset);
        return node;
    }
}