关于java:二叉树框架６

中序遍历对BST十分重要，之前也讲过了BST的基本操作。(东哥总结的是真的强)

不同的二叉搜寻树

给定一个正整数n,请你计算，存储{1,2,3…n}这些值共有多少种不同的BST构造。
还是那句老话，二叉树算法的关键在于明确根节点须要做什么。
假如给算法输出５，也就是说用{1,2,3,4,5}这些数字去结构BST。
首先，这棵BST的根节点总共有几种状况？
显然有５中，因为1-5都能够作为BST的根节点对吧。而后咱们固定住一个根节点，而后再进行剖析，这个时候有几种不同的BST呢？
比方树把3固定住，去剖析其余树节点都可能的状况。
依据BST的性质，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。所以如果固定3为根节点，左子树节点就是{1,2}的组合，右子树就是{4,5}的组合。
左子树的组合数和右子树的组合数乘积就是3为根时的BST个数。

下面讲的是以3为根的状况，其余节点也是一样的。
[1,2]和[4,5]有几种组合呢？
排列组合公式 2*2=4种，也就是说咱们的后果就是左右子树组合的乘积。
应用递归函数

//闭区间[lo,hi]的数字能组成count(lo,hi)种BST
int count(int lo,int hi);

依据这个函数的定义，联合方才的剖析，能够写出代码

//主函数
int numTrees(int n){
//计算闭区间[1,n]组成的BST的个数
return count(1,n);
}

//计算闭区间[lo,hi]组成的BST个数
int count(int lo,int hi){
//base case
if(lo>hi){
return 1;
}

int res=0;
for(int i=lo;i<=hi;i++){
//i的值作为根节点root
int left=count(lo,i-1);
int right=count(i+1,hi);
//左右子树的组合数乘积是BST的总数
res+=left*right;
}
}