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
confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.
Subscribe to see which companies asked this question
//递归的方法
class Solution{
public:
vector<TreeNode*> generateTrees(int n){
return generate(1, n);
}
vector<TreeNode*> generate(int begin, int end){
vector<TreeNode*> res;
if (begin > end) res.push_back(NULL);
if (begin == end) res.push_back(new TreeNode(begin));
if (begin < end)
{
for (int k = begin; k <= end; k++){
vector<TreeNode*> l = generate(begin, k - 1);
vector<TreeNode*> r = generate(k + 1, end);
for (int i = 0; i < l.size(); i++)
{
for (int j = 0; j < r.size(); j++)
{
TreeNode* node = new TreeNode(k);
node->left = l[i];
node->right = r[j];
res.push_back(node);
}
}
}
}
return res;
}
};
LeetCode 95:Unique Binary Search Trees II
原文：http://blog.csdn.net/geekmanong/article/details/50448707