二叉树的后序遍历序列：

题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析：

后序遍历：左->右->根

二叉搜索树定义：一个二叉树，它的每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。(即小的在左，大的在右）

根据后序遍历的顺序，我们可以知道数组的最后一个节点一定是二叉树的根节点，那么前面的序列，一部分是左子树（都比根节点小），另一部分是右子树（都比根节点大）。此后，可以递归地进行判断，左子树序列中的最后一个元素是左子树跟节点，比它小的是其左子树，比它大的是其右子树。·····以此类推，如果存在在左子树序列中出现比根节点大的，或者右子树序列中比根节点小的情况，那么就说明不是二叉搜索树的后序遍历序列。

代码:

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        if (sequence.length == 1) return true;
        return judge(sequence,0,sequence.length-1);
    }

    public static boolean judge(int[] sequence, int start, int end) {
        //当起始位置大于终止位置的时候，说明这颗子树为空，直接返回true即可。
        if(start>end) return true;
        int root = sequence[end];
        //找到左子树序列的起始位置，起点是start，终点是首个大于根节点元素的前面一个元素
        int lefts = start;
        for(;lefts<end-1;lefts++){
            if(sequence[lefts]>root) break;
        }
        //右子树序列，即从首个大于根节点的元素到根节点的前一个元素，判断这个序列中是否每个元素都大于根节点
        int rights  = lefts;
        for(;rights<end-1;rights++){
            if(sequence[rights]<root) return false;
        }
        //递归调用，判断是否左子树和右子树的结构满足二叉搜索树的结构
        boolean isleft = judge(sequence,start,lefts-1);
        boolean isright = judge(sequence,rights,end-1);
        return isleft && isright;
    }
}

小结：

对于这种输入是一个int[] 数组的函数，我们进行二分递归操作的时候，需要记录它的起始位置和终止位置，这样才能进行递归。