Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Unique Binary Search TreesII
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
分析：这个题目是要求BST有多少种排列方式，第一题是只求数量，第二题要求把结构也存储下来。本质都是深搜，第一题显然更简单
因为只要知道当前有多少个数，就可以知道有多少种排列方式了，甚至可以简单的建个存储表，更快一些。而第二题就需要将当前情况
下所有点的排列搞到，返回上一级，上一级再建立更高一层的bst
第一题代码：
class Solution {
public:
int numTrees(int n) {
if(n==) return ;
if(n==) return ;
int wnum = ;
for(int i=;i<=n;i++)
{
wnum += numTrees(i-) * numTrees(n-i);
}
return wnum;
}
};
第二题代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode *>builtree(int left,int right)
{
vector<TreeNode *>data;
if(left>right)
{
data.push_back(nullptr);
return data;
} vector<TreeNode *>leftr,rightr;
for(int i=left;i<=right;i++)
{ leftr = builtree(left,i-);
rightr = builtree(i+,right);
for(int t1=;t1<leftr.size();t1++)
for(int t2=;t2<rightr.size();t2++)
{
TreeNode *nod = new TreeNode(i);
nod->left = leftr[t1];
nod->right = rightr[t2];
data.push_back(nod);
}
}
return data; }
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode *> data(,nullptr);
data = builtree(,n);
return data;
}
};