# LeetCode 95:Unique Binary Search Trees II

Datetime:2016-08-23 01:22:31         Topic: LeetCode          Share        Original >>

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;
}
};```