题目描述

解题思路

详细链接🔗

二叉搜索树的定义：
左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。（这是返回false的条件）

分治的思想

后序遍历可以直到最后一个是根节点。所以我们需要根据根节点的大小来分左右区间。
例如：[1,6,3,2,5] ，可以知道，根节点为5，那么找到第一个大于五的索引 index，那么index之后的数字都必须要大于5，因为在右子树，此时index之前的必须要小于5（但这里可以不用判断，因为寻找index的时候已经判断）。

public boolean verifyPostorder(int[] postorder) {
    return traversal(postorder, 0, postorder.length - 1);
}
public boolean traversal(int[] postorder, int left, int right) {
    if (left >= right) {
        return true;
    }
    int index = left;
    while (postorder[index] < postorder[right]) index++;
    int temp = index;
    while (postorder[temp] > postorder[right]) temp++;
    return temp == right && traversal(postorder, left, index - 1) && traversal(postorder, index, right - 1);
}

倒后序遍历（栈实现）

倒后序遍历也就是中右左。
这里说一下流程，详细参考上边链接：
他们的大小关系：

1. 使用一个栈存储依次递增的节点值
2. 每当遇到值递减的ri，那么出栈更新根节点，因为此时判断左子树。
3. 每轮判断 ri 和 root 的值关系：

若 ri >root 则说明不满足二叉搜索树定义，直接返回 false 。
若 ri <root 则说明满足二叉搜索树定义，则继续遍历。

// 单调栈
public boolean verifyPostorder(int[] postorder) {
    Stack<Integer> stack = new Stack<>();
    int rootVal = Integer.MAX_VALUE;
    // 到后序遍历
    for (int i = postorder.length - 1; i >= 0; i--) {
        if (postorder[i] > rootVal) return false;
        while (!stack.isEmpty() && postorder[i] < stack.peek()) {
            rootVal = stack.pop();
        }
        stack.push(postorder[i]);
    }
    return true;
}