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

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

这个题没啥好说的，就是靠思路，因为是后序遍历，数组最右边的一定是根节点，我们先向前找比根节点小的第一个数。那么这个数以及其左手边就是左子树，这个数右边到倒数第二个数就是右子树，然后我们创建一个helper方法，如果左子树中有比根节点大的，返回false，右子树中有比根节点小的，同样返回false，否则的话就一直递归下去知道数组长度小于2。代码如下：

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length < 2){
            return true;
        }
        int last = postorder.length - 1;
        int i = last;
        for(; i >=0; i--){
            if(postorder[i] < postorder[last]){
                break;
            }
        }
        return verify(Arrays.copyOfRange(postorder,0,i+1), Integer.MIN_VALUE, postorder[last]) && verify(Arrays.copyOfRange(postorder,i+1,last), postorder[last], Integer.MAX_VALUE);
    }

    private boolean verify(int[] postorder, int min, int max){
        if(postorder.length < 2){
            return true;
        }
        int last = postorder.length - 1;
        int i = last;
        for(; i >=0; i--){
            if(postorder[i] > max || postorder[i] < min){
                return false;
            }
            if(postorder[i] < postorder[last]){
                break;
            }
        }
        return verify(Arrays.copyOfRange(postorder,0,i+1), Integer.MIN_VALUE, postorder[last]) && verify(Arrays.copyOfRange(postorder,i+1,last), postorder[last], Integer.MAX_VALUE);
    }
}