Given 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 分析：这道题与unique binary search tree I不同在于我们要生成所以的二叉查找树并返回树的根。同样我们用递归的方法，如果是空树我们加入一个NULL指针，这个对于简化代码是有帮助的。
如果在空树的情况是我们不加入NULL,而是让<TreeNode *> res为空，那么在通过左右两个子树组成新树时，代码会繁琐很多。因为我们必须要处理左子树、右子树是否为空总共四种情况。
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
return generate_Trees(,n);
}
vector<TreeNode *> generate_Trees(int l, int r){
vector<TreeNode *> result;
if(l > r)
result.push_back(NULL);
for(int i = l; i <= r; i++){
vector<TreeNode *> left = generate_Trees(l, i-);
vector<TreeNode *> right = generate_Trees(i+, r);
for(auto j:left)
for(auto k:right){
TreeNode *root = new TreeNode(i);
root->left = j;
root->right = k;
result.push_back(root);
}
}
return result;
}
};