package jianzhiOffer;
/**
* 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
* 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
* @author user
* 思路：要判断该数列是否是二叉树的后序遍历，及判断此数列是否满足规则
* 即左子树始终小于根节点，右子树始终大于根节点
* 1、找到根节点，划分出左右子树
* 2、判断左右子树是否满足规则
* 3、假如以上判断正确，则将左右子树当做新的数列，重复以上操作，判断这两个
* 数列是否满足规则
*/
public class ch23 {
public boolean VerifySquenceOfBST(int [] sequence) {
int len = sequence.length;
if(len == 0) return false;
if(len == 1) return true;
return isTreeBST(sequence,0,len - 1);
}
public static boolean isTreeBST(int[] sequence,int start,int end) {
if(end <= start) return true;
int i = start;
for (; i < end; i++) {
if(sequence[i] > sequence[end]) break;
}
for (int j = i; j < end; j++) {
if(sequence[j] < sequence[end]) return false;
}
return isTreeBST(sequence, start, i - 1) && isTreeBST(sequence, i, end - 1);
}
}
剑指offer23
原文：http://blog.51cto.com/12222886/2063319
