请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

提示：

数组长度 <= 1000
postorder 中无重复数字

代码

class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder == null){
return true;
}

    return f(postorder, 0, postorder.length - 1);
}

boolean f(int[] postorder, int i, int j){
    if(i >= j){
        return true;
    }

    int root = postorder[j];
    int p = i;
    // 获取第一个大于或者等于 root 等元素的位置
    while(postorder[p] < root) p++;
    // 判断 p ~ j -1 这个范围是否存在小于root的元素
    for(int k = p; k < j; k++){
        if(postorder[k] < root){
            return false;
        }
    }

    return f(postorder, i, p - 1) && f(postorder, p, j - 1);
}

}

时间复杂度：最差O(n^2)
空间复杂度：最差(n)（退化成链表）