面试题33. 二叉搜索树的后序遍历序列

题目描述：

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

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

数组长度 <= 1000

思路：

1、在后续遍历所得的序列中，最后一个数字是树的根节点的值；
2、数组中前面的数组可以分为两部分：第一部分是树的左子树，它们都比根节点的值小，第二部分是树的右子树，它们都比根节点的值大；
3、我们再用相同的办法确定左右子树的结构，这就是一个递归的过程。
4、递归过程：确定左右子树的左右边界，右边界的值一定是当前子树的根节点的值；从头开始遍历，当找到第一个比根节点大的数，这个数前面的就是左子树，从这个值起，后面的就是右子树。如果后面的数有一个比根节点小，就不满足条件，返回false；在递归过程中，要考虑只有左子树，或者只有右子树的情况；

Java解法（递归）：

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null) return false;
        if(postorder.length <= 2) return true;
        return verifysub(postorder, 0, postorder.length - 1);
    }

    public boolean verifysub(int[] subarry, int left, int right)
    {
        if(left >= right) return true;
        int root = subarry[right];
        int mid = left;
        for(; mid < right; mid++)
        {
            if(subarry[mid] > root) break;
        }
        int j = mid;
        for(; j < right; j++)
        {
            if(subarry[j] < root) return false;
        }
        return verifysub(subarry, left, mid -1) && verifysub(subarry, mid, right -1);
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof