给你一个树的后序遍历集，判断其是否为二叉搜索树

力扣链接：剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（LeetCode） (leetcode-cn.com)

思路

已知后序遍历为：左子树->右子树->根结点，将其后序遍历结果数组反转后变为：根结点->右子树->左子树

如果其符合二叉搜索树的定义，那么它的右子树必然比根结点大，左子树必然比根结点小

我们使用一个单调栈（单调递增），对于根结点和右子树来说其满足单调栈的条件，对于左子树来说则不满足单调栈的条件，

当遇到数组元素小于单调栈顶部元素时，我们可知现在已经遍历到树的左子树部分，则弹出树的根结点和右子树，直到数组元素大于等于单调栈顶部元素

为什么要直到数组元素大于等于单调栈顶部元素，而不是直接清空单调栈，因为右子树的左子树也要比根结点大

对左子树进行同样的操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 记录前一个根结点的值
        int root = Integer.MAX_VALUE;
        // 单调栈
        Stack<Integer> stack = new Stack<>();
        // 从后往前遍历数组
        for (int i = postorder.length-1; i >= 0; i--) {
            // 如果当前结点值大于前一个根结点的值，则不满足右子树的左子树也要比根结点大
            // 即不满足二叉搜索树的定义，返回false
            if (postorder[i]>root){
                return false;
            }
            // 此时已经遍历完根结点和右子树，遍历到左子树
            while(!stack.isEmpty() && stack.peek()>postorder[i]){
                // 弹出栈元素，并记录根结点的值
                root = stack.pop();
            }
            // 往单调栈中添加元素
            stack.add(postorder[i]);
        }
        return true;
    }
}

例图：例图