中序遍历对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)种BSTint 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 caseif(lo>hi){return 1;}int res=0;for(int i=lo;i<=hi;i++){//i的值作为根节点rootint left=count(lo,i-1);int right=count(i+1,hi);//左右子树的组合数乘积是BST的总数res+=left*right;}}