判断整数序列是不是二叉查找树的后序遍历结果
定义：二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树。
/* * 判断给定序列是否为二叉查找树*/public class JudgePostOrderSearchTree {static boolean ifIsPostOrderSerachTree(int[] array,int start,int end) { //从start到end-1if(array == null || start > end )return false;if(start == end) //序列中只有一个数return true;int root = array[end-1];int i=start;while( array[i] < root && i<end-1) //找到第一个大于根的数的位置positioni++;int position = i;while( i<end-1) {if(array[i] <root) { //如果在position后还有小于根的数，则不是二叉查找树return false;}i++;}//若左右子树有一个不为二叉查找树，则当前序列不满足条件boolean left = true;left = ifIsPostOrderSerachTree(array,start,position);boolean right = true;right = ifIsPostOrderSerachTree(array,position,end-1);return (left && right);} public static void main(String[] args) {int[] a = {5,7,6,9,11,10,8};System.out.println(ifIsPostOrderSerachTree(a,0,a.length));int[] b = {7,4,6,5};System.out.println(ifIsPostOrderSerachTree(b,0,b.length));}}