剑指 Offer 33. 二叉搜索树的后序遍历序列

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

• 划分左右子树： 遍历后序遍历的 [i,j] 区间元素，寻找 第一个大于根节点 的节点，索引记为 m 。此时，可划分出左子树区间 [i,m-1]、右子树区间 [m, j - 1] 、根节点索引 j
• 使用子函数（左右子树对应的数组范围一直在变 定义low、high）
• 定义p指针：从left开始，遍历左子树找出mid（mid=p），判断右子树（if(p!=right)）
• 检查左右子树

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return sub(postorder,0,postorder.length-1);

    }
    boolean sub(int[] postorder,int left,int right){
        if(left>=right){
            return true;//已经遍历结束了
        }
        int p=left;//从最开始遍历左右子树
        while(postorder[p]postorder[right]){//遍历右子树
            p++;
        }
        if(p!=right){//也就是说还没到根节点，右子树的遍历就中止了，即右子树中存在比根节点要少的
            return false;
        }
        return sub(postorder,left,mid-1)&&sub(postorder,mid,right-1);//右子树是道j-1
    }
}