# LeetCode题目：Unique Binary Search Trees II

By | 2012 年 11 月 4 日

Unique Binary Search Trees II
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.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode *copyTree(TreeNode *root) {
if(NULL == root) return NULL;
TreeNode *croot = new TreeNode(root->val);
croot->left = copyTree(root->left);
croot->right = copyTree(root->right);
return croot;
}
vector generateTrees(int startval,int endval) {
vector ret;
if(endval < startval) {
ret.push_back(NULL);
}
else {
for(int rootval = startval; rootval <= endval; ++rootval) {
vector temp;
{//push root into ret
TreeNode *root = new TreeNode(rootval);
temp.push_back(root);
}
//process the left subtrees
vector lefts = generateTrees(startval, rootval - 1);
int count = temp.size();
for(int ti = 0; ti < count; ++ti) {
TreeNode *root = temp[0];
temp.erase(temp.begin());
for(int li = 0; li < lefts.size(); ++li) {
TreeNode* left = lefts[li];
TreeNode *newroot = copyTree(root);
newroot->left = left;
temp.push_back(newroot);
}
//if(root) delete root;
}
//process the right subtrees
vector rights = generateTrees(rootval + 1, endval);
count = temp.size();
for(int ti = 0; ti < count; ++ ti) {
TreeNode *root = temp[0];
temp.erase(temp.begin());
for(int ri = 0; ri < rights.size(); ++ri) {
TreeNode *copyExpand = copyTree(root);
copyExpand->right = rights[ri];
temp.push_back(copyExpand);
}
//if(root) delete root;
}
for(int i = 0; i < temp.size(); ++i) {
ret.push_back(temp[i]);
}
}
}
return ret;
}
public:
vector generateTrees(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return generateTrees(1,n);
}
};
```