判断整数序列是不是二叉查找树的后序遍历结果

定义：二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树。

/*
 * 判断给定序列是否为二叉查找树*/

public class JudgePostOrderSearchTree {

	static boolean ifIsPostOrderSerachTree(int[] array,
						int start,int end) { //从start到end-1
		if(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) //找到第一个大于根的数的位置position
			i++;
		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));		

	}

}

算法思想参考了http://www.cnblogs.com/Jessy/archive/2010/11/03/1868289.html