剑指 Offer.33-二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    boolean recur(int[] postorder,int i,int j){
        // 当到达单个节点的时候 直接返回true
        if(i>=j) return true;
        int p = i;
        // 验证当前根节点左子树节点的合法性
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        // 验证当前节点右子树节点的合法性
        while(postorder[p] > postorder[j]) p++;
        // 当前树的合法性 当前树的左右节点序列合法，递归验证左右子树
        return p == j && recur(postorder,i,m-1) && recur(postorder,m,j-1);
    }
}

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            // 若节点大于当前节点 则正常入栈
            // 当遇到递减元素时，更新root至最接近当前节点的值
            // 当前节点进栈 通过单调栈辅助验证序列合法性
            while(!stack.isEmpty() && stack.peek() > postorder[i])
            	root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}