关于java:二叉树框架６

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

不同的二叉搜寻树

给定一个正整数 n, 请你计算，存储 {1,2,3…n} 这些值共有多少种不同的 BST 构造。
还是那句老话，二叉树算法的关键在于明确根节点须要做什么。
假如给算法输出5，也就是说用 {1,2,3,4,5} 这些数字去结构 BST。
首先，这棵 BST 的根节点总共有几种状况？
显然有5中，因为 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;
}
}