95. Unique Binary Search Trees II
题目描述：
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
题目翻译
对给定的数字 n，生成所有储存了数字 1 至 n 的结构不同的 BST's （二叉查找树）。
举个栗子 ⊙o⊙，
假如给定的 n = 3，你的程序应该返回如下图所示的5个不同的二叉查找树。
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解题方案
标签： Tree
思路：
这道题是 Unique Binary Search Trees 的升级版，解决方法同样是动态规划。在做 Unique Binary Search Trees 这道题时，我们用一个数组保存 1 至 n-1 对应的不同二叉树的个数 X1、X2、X3、... Xn-1，则 n 对应的不同二叉树个数
Xn = Xn-1 + X1*Xn-2 + X2*Xn-3 + X3*Xn-4 + ... + Xn-2*X1 + Xn-1通过这个递推式，我们可以从 N = 1 开始递推，最后得到 N = n 时不同二叉查找树的个数。
与上述思路类似，我们可以通过深度优先搜索（递归）解决这道题。因为二叉查找树满足父节点的值大于左子节点的值，小于右子节点的值，所以我们可以：
- (1) 从 N=1 开始构建二叉查找树，则它的左子树节点数为 0，右子树节点数为 n-1；
- (2) N=2 时，左子树节点数为 1，右子树节点数为 n-2；
- ……
- (n) N=n 时，左子树节点数为 n-1，右子树节点数 0。
而在第(1)步中，右子树继续执行上述循环，子树的子树又执行这个循环，最终，我们可以将子树节点数减少到 1，而一个节点只有一种排列方式，所以此时可以毫不犹豫地将结果返回给上一级。然后包含有两个节点的二叉树排列方式又被返回给上一级。……
依此类推，我们最后可以得到所有不同结构的二叉查找树。
代码：
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
return GenerateSubTree(1, n + 1);
}
vector<TreeNode*> GenerateSubTree(int l, int r) {
vector<TreeNode *> subTree;
if (l >= r) {
subTree.push_back(NULL);
return subTree;
}
if (l == r - 1) {
subTree.push_back(new TreeNode(l));
return subTree;
}
for (int i = l; i < r; ++i) {
vector<TreeNode *> leftSubTree = GenerateSubTree(l, i);
vector<TreeNode *> rightSubTree = GenerateSubTree(i + 1, r);
for (int m = 0; m < leftSubTree.size(); ++m) {
for (int n = 0; n < rightSubTree.size(); ++n) {
TreeNode *root = new TreeNode(i);
root->left = leftSubTree[m];
root->right = rightSubTree[n];
subTree.push_back(root);
}
}
}
return subTree;
}
};