# 【一天一道LeetCode】#95. Unique Binary Search Trees II

2016-06-18 09:01:34         来源：ZeeCoder

## （一）题目

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.

## （二）解题

``````struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void GetTreeSize(TreeNode* head,int &num)
{
{
num++;
}
else return;
}
bool isInTree(TreeNode* head , int tar)
{
TreeNode* p = head;
while(p!=NULL)
{
if(tar>p->val) p = p->right;
else if(tarval) p = p->left;
else return true;
}
return false;
}
void dpBSTrees(int& n , int i , vector& isVaild , int count , TreeNode* head,TreeNode* temp, vector& ret)
{
int size = 0;
if (size==n) {
return;
}

bool isleft = false;
bool isright = false;
for(int j = i-1 ; j>=1 ; j--)
{
{
temp->left = new TreeNode(j);
isleft= true;
}
}
for(int z = i+1 ; z<=n ; z++)
{
{
temp->right = new TreeNode(z);
isright = true;
}
}
if (isright||isleft)
{
temp=NULL;
}
}

vector generateTrees(int n) {
vector ret;
vector isVaild(n+1,true);
int count = 0;
for(int i = 1 ; i <= n ; i++)
{
TreeNode* head = new TreeNode(i);
isVaild[i] = false;