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

方式一：递归

思路：后续遍历得到的序列中最后一个元素一定是树的根节点的值。数组中前面的数字可以分为两部分：左子树的值序列和右子树的值序列。左子树值都小于根节点值，右子树值都大于根节点值。
确定了左子树值和右子树值的序列，还是按上面的方法确定对应的子树的结构，这是一个递归的过程。如果递归过程中发现其右子序列中有值小于根值，那么这不是一个后序序列。

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

    private boolean verify(int[] postorder, int first, int last) {
        if (last - first <= 1) {
            return true;
        }
        // 后序遍历，其root一定是最后一个
        int rootVal = postorder[last];
        int curIndex = first;
        while (curIndex < last && postorder[curIndex] <= rootVal) {
            curIndex++;
        }
        // 找到比curIndex大的下标，则是其右子树序列中的值
        // 这个值如果比根节点小，则说明这不是一个后序遍历
        for (int i = curIndex; i<last;i++) {
            if (postorder[i] < rootVal) {
                return false;
            }
        }
        // 继续递归，将后序遍历数组分成两部分
        // curIndex在这里是右子树后序序列的开始
        return verify(postorder, first, curIndex - 1) && verify(postorder, curIndex, last - 1);
    }