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.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解法類似 241題：http://www.reibang.com/p/91b3c4352b43
Solution1：Divide and Conquer
以每個(gè)num=0...n都嘗試作為起點(diǎn)敢会，以num分成左右兩部分part1 for [0..num - 1], part2 for [num + 1, n] (Divide)阱冶，recursiely計(jì)算part1和part2的建樹結(jié)果茎用，再將這兩個(gè)組合結(jié)果Conquer構(gòu)成從當(dāng)前num分的結(jié)果描验。
Time Complexity: 框沟？ Space Complexity: 梁呈？
Solution2：Divide and Conquer + Hashmap
Solution1中含有重復(fù)計(jì)算嘁锯，2在Solution1的基礎(chǔ)上 將已求過的[start, end]的結(jié)果 Map<String, List<TreeNode>> cached_tree保存下來掂林，緩存避免重復(fù)計(jì)算粘我。
Time Complexity: 鼓蜒？ Space Complexity: 痹换？
Solution3：DP寫法
ret[n] 保存到n的結(jié)果(所有的unique BST)
根據(jù)96. Unique Binary Search Trees: http://www.reibang.com/p/a49119ef97c3
的DP遞推表達(dá)式
G(n): the number of unique BST for a sequence of length n.
F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.
G(0)=1, G(1)=1.
G(n) = F(1, n) + F(2, n) + ... + F(n, n).
F(i, n) = G(i-1) * G(n-i) 1 <= i <= n
So,
=> G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
思路相同，這不過這里是把G當(dāng)作實(shí)際的BSTs都弹，G(0) 和 G(n-1) 做組合娇豫，G(1) * G(n-2)做組合，...都加到結(jié)果中畅厢。做組合時(shí)樹：node.value = j, 左側(cè)的是left children冯痢，右側(cè)的是right children(需shift)，
Example G(4) 如下圖所示：
n = sum of the total number of unique binary trees
Time Complexity: n框杜？ Space Complexity: n浦楣？
Solution1 Code：
class Solution1 {
public List<TreeNode> generateTrees(int n) {
if(n == 0) return new ArrayList<TreeNode>();
return genTrees(1,n);
}
public List<TreeNode> genTrees (int start, int end) {
List<TreeNode> list = new ArrayList<TreeNode>();
if(start > end) list.add(null);
else if(start == end) list.add(new TreeNode(start));
else {
// start < end
List<TreeNode> left,right;
for(int i = start; i <= end; i++) {
// Divide
left = genTrees(start, i - 1);
right = genTrees(i + 1, end);
// Conquer
for(TreeNode lnode: left) {
for(TreeNode rnode: right) {
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
list.add(root);
}
}
}
}
return list;
}
}
Solution2 Code：
class Solution2 {
public List<TreeNode> generateTrees(int n) {
if(n == 0) return new ArrayList<TreeNode>();
return genTrees(1,n);
}
private Map<String, List<TreeNode>> cached_tree = new HashMap<>();
public List<TreeNode> genTrees (int start, int end) {
// find if there has been cached already
String key = "" + start + "." + end;
if(cached_tree.containsKey(key)) return cached_tree.get(key);
List<TreeNode> list = new ArrayList<TreeNode>();
if(start > end) list.add(null);
else if(start == end) list.add(new TreeNode(start));
else {
// start < end
List<TreeNode> left,right;
for(int i = start; i <= end; i++) {
// Divide
left = genTrees(start, i - 1);
right = genTrees(i + 1, end);
// Conquer
for(TreeNode lnode: left) {
for(TreeNode rnode: right) {
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
list.add(root);
}
}
}
}
cached_tree.put(key, list);
return list;
}
}
Solution3 Code：
class Solution3 {
// G(0)=1, G(1)=1.
// G(n) = F(1, n) + F(2, n) + ... + F(n, n).
// F(i, n) = G(i-1) * G(n-i) 1 <= i <= n
// =>
// G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
public List<TreeNode> generateTrees(int n) {
if(n == 0) return new ArrayList<TreeNode>();
// dp init
List<TreeNode>[] res = new List[n+1];
res[0] = new ArrayList();
res[0].add(null);
res[1] = new ArrayList();
res[1].add(new TreeNode(1));
// dp
for(int i = 2; i <= n; i++){
res[i] = new ArrayList();
for(int j = 1; j <= i; j++){
for(TreeNode nodeL: res[j - 1]){
for(TreeNode nodeR: res[i - j]){
TreeNode node = new TreeNode(j);
node.left = nodeL;
node.right = clone(nodeR, j);
res[i].add(node);
}
}
}
}
return res[n];
}
private TreeNode clone(TreeNode n, int offset) {
if (n == null) {
return null;
}
TreeNode node = new TreeNode(n.val + offset);
node.left = clone(n.left, offset);
node.right = clone(n.right, offset);
return node;
}
}
