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
思路：
遇到二叉树，多半是分为左右子树两个问题递归下去。
由序列[1,…,m]和[i+1,…,i+m]能够构造BST的数目是相同的，不妨将原问题转化为求n个连续的数能够构成BST的数目
考虑分别以1,2,…i…,n为root，左子树由1~i-1这i-1个数构成，右子树有i+1~n这n-i-2个数构成，左右子树数目相乘即可，然后再累加
代码：
int numUniTrees(int n, vector<int> &res){
if(res[n] != -)
return res[n];
if(n == ||n == ){
res[n] = ;
return res[n];
}
int num = ;
for(int i = ; i < n; i++){
//num += numTrees(i)*numTrees(n-i-1);//剥离出来一个函数之后，注意更改函数名
num += numUniTrees(i, res) * numUniTrees(n-i-, res);
}
res[n] = num;
return res[n];
}
int numTrees(int n) {
if(n < )
return ;
vector<int>res(n+, -);
return numUniTrees(n, res);
}