33-二叉搜索树的后续遍历序列

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

如下二叉树:

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

上图的后序遍历序列是 4 9 5 13 22 18 12

可以看到，根节点12是序列的最后一个值，然后以12为分割点，可以将序列分为两部分，前一部分是左子树，结点值都小于12;后一部分是右子树，结点值都大于12。然后因为左子树右子树也是后序遍历，所以就可以递归的判断。那么什么情况说明不是后序遍历序列呢？那就是当以根节点不能分成两部分时。比如 4 7 5 9 10 6 这个序列，根据6 可以分为 4 和 7 5 9 10 但是在后半部分中5小于6，这就说明这个序列是错误的。

  public boolean verifyPostorder(int[] postorder) {
        if (postorder == null) {
            return false;
        }
        int length = postorder.length;
        return isPostorder2(postorder, 0, length - 1);
    }

  public boolean isPostorder2(int[] post, int begin, int end) {
        if (begin >= end) {
            return true;
        }
        int p = begin;
        int root = post[end];
        while(post[p] < root) { //从头找到小于root的值，直到遇到大于root的值
            p++;
        }
        int m = p;
        while (post[p] > root) { //找大于root的值，直到遇到小于root的值
            p++;
        }
        //以上两个while循环不会出界，因为序列里元素是不重复的
        return p == end  //如果p可以走到end位置，说明[begin,end-1]可以分成前一段小于root，后一段大于root。
          && isPostorder2(post, begin, m - 1) && isPostorder2(post, m, end - 1);
    }