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.
\ / / / \ \
/ / \ \
3
[1] [4] [5] [3] [2]
=====================BST树,平衡查找树
如果将上图中的实例按照[1]..[5]的下标来摆放,
以1为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是0个元素的树,右子树是2个元素的树.
以2为根的树的个数,等于左子树的个数乘以右子树的个数,左子树的元素个数为1,右子树元素个数为为1
...以此类推
========
当数组1,2,3...n时,基于一下原则构建BST树具有唯一性:以i为根节点的树,其左子树由[1,i-1]构成
其右子树由[i+1,n]构成.
定义f(i)为以int a[]=[1,i]能产生的Uniuqe BST的数目,
那么如果a[]为空,那么只有一种BST,即空树,f(0)=1
if a.size==1,单个节点,那么只有一种BST,f(1)=1
if a.size==2,有如下两种可能
1 2
\ /
2 1
f(2) = f(0)*f(1), 1为根的情况
+f(1)*f(0), 2为根的情况
if a.size==3,那么
f(3) = f(0)*f(2)//root=1
+f(1)*f(1)//root=2
+f(2)*f(0)//root=3
可以发现f的递归公式为
==========
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
///
vector<TreeNode*> generateTrees(int n){
if(n==) return generateTrees(,);
return generateTrees(,n);
} vector<TreeNode*> generateTrees(int start,int end){
vector<TreeNode*> subTree;
if(start>end){
subTree.push_back(nullptr);
return subTree;
} for(int k = start;k<=end;k++){
vector<TreeNode*> leftSubs = generateTrees(start,k-);
vector<TreeNode*> rightSubs = generateTrees(k+,end);
for(auto i:leftSubs){
for(auto j:rightSubs){
TreeNode *node = new TreeNode(k);
node->left = i;
node->right = j;
subTree.push_back(node);
}
}
}
return subTree;
}
};