题目
Given an integer 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.
Input:
BST的最大值（BST范围1-n）:: Integer
Output:
由1~ n组成的所有BST :: List<TreeNode>
Recursion 解法
Intuition：
这道题呐，其实Recursion的想法很容易想，我们依次遍历每个数，把这个数当初Root，那么比这个数小的数都当成左子树，比这个数大的数都当成右子树。退出Recursion的条件自然是左边界大于右边界啦。
Edge Case:
if (n <= 0){
return new ArrayList<TreeNode>();
}
Code:
public List<TreeNode> UniBST(int n){
//edge cases
if (n <= 0){
return new ArrayList<TreeNode>();
}
return helper(1, n);
}
public List<TreeNode> helper(int left, int right){
List<TreeNode> res = new ArrayList<>();
if (left > right){
res.add(null);
return res;
}
for (int i = 1; i <= n; i++){
List<TreeNode> left = helper(left, i - 1);
List<TreeNode> right = helper(i + 1, right);
for (TreeNode l: left){
for (TreeNode r: right){
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
DP 解法
但是这道题居然还可以用DP解而且解法比较匪夷所思...
首先，根据DP的本质是当前问题是基于之前的子问题来解决的。那么这道题我们是想建一个拥有n个node的树，很自然的想到能不能在利用n-1个node的树。
一步步来哈，左边的树好想啊， 1 到 n-1 的数组成的树肯定每个node的值都比n小啊，那这个树可以直接拿来安到左边当做子树就好。
Tricky的部分在于我们怎么通过n-1个node建成的树来得出n个node树的右子树呢？最明显的问题就是值不够大呀。怎么办？没有条件创造条件也要上啊（￣︶￣）↗， 我们不是想右边子树的值都大于n么？那么就直接在之前已经建好的某个树所有的node都加n就好了。
还有要注意的一点就是子树的选择要确保他们node的个数加1（root）是等于n的。
和所有的DP一样，我们需要有个DP array， 而因为我们依赖于n-1个node的树（可能不止一种），那么这个array里面存的就应该是List<TreeNode>,即
List<TreeNode>[] dp = new List<TreeNode>[n + 1];
起始状态 是0 个node，没法建树，那么index为0对应的那个List<TreeNode>里放 null
是不是还是一脸懵逼😳？没关系我们跑个🌰
来看看n = 3的情况吧
n = 1 和 n = 2的情况比较trivial，我们跳过， 假设0 ~ 2 的dp array我们已经填好了，应该是这个样子滴：
那么此时我们可以选择可以作为子树的的root范围是0 ~ 2
意义上可以表示为:
要建一个3个node的树，假如取一个含0个node的树作为左子树 即为dp[0]里存的树, 新的root的值应该比左子树最大值大1， 即为1。 右子树取剩下的node， 即为 3 - 0 - 1 = 2， 也就是dp[2]里存的树, 但是右子树我们还要进一步处理让他比新的root大，那么加offset 1，注意这是dp[2]里已经有两个树。最终得到的树为也有两种可能：
Code:
TC: O(n^4) SC: O(n^2)?
public List<TreeNode>UniqueBST(int n){
if (n == 0){
return new ArrayList<TreeNode>(null);
}
//initialize
List<TreeNode>[] dp = new List<TreeNode>[n + 1];
dp[0].add(null);
for (int i = 1; i <= n; i++){ //select total number of nodes in a tree
dp[i] = new ArrayList<>();
for (int j = 0; j < i; j++){ //select number of nodes in left subtree
for (TreeNode l: dp[i]){
for (TreeNode r: dp[i - 1 - j]){ //select number of nodes in right subtree
TreeNode newRoot = new TreeNode(j + 1);
newRoot.left = l;
newRoot.right = addOffset(r, j + 1);
dp[i].add(newRoot);
}
}
}
}
return dp[n];
}
public TreeNode addOffset(TreeNode root, int offset){
if (root == null){
return null;
}
TreeNode res = new TreeNode(root.val + offset);
res.left = addOffset(root.left, offset);
res.right = addOffset(root.right, offset);
return res;
}
Reference
https://discuss.leetcode.com/topic/2940/java-solution-with-dp
https://leetcode.com/problems/unique-binary-search-trees-ii/description/
