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

示例 1：

输入: postorder = [4,9,6,5,8]
输出: false
**解释：**从上图可以看出这不是一颗二叉搜索树

示例 2：

输入: postorder = [4,6,5,9,8]
输出: true
**解释：**可构建的二叉搜索树如上图

提示：

数组长度 <= 1000

postorder 中无重复数字

二叉搜索树，左子树元素小于root，右子树大于root

后序遍历结果为[左子树后序，右子树后序，root]

所以我们可以直接找到一个子树的范围，然后判断另一个子树元素是否满足均小于/大于root

满足则继续判断两个子树内部情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool verifyTreeOrder(vector<int> &postorder) {
        if (postorder.empty())
            return true;
        return check(postorder, 0, postorder.size() - 1);
    }
    bool check(vector<int> &postorder, int l, int r) {
        if (l >= r)
            return true;
        int i = r - 1;
        while (i >= l && postorder[i] > postorder[r])
            i--;
        for (int j = l; j <= i; j++)
            if (postorder[j] >= postorder[r])
                return false;
        return check(postorder, l, i) && check(postorder, i + 1, r - 1);
    }
};

注意到从右往左遍历时，

升序元素一定是前一个元素的右子结点，

第一个降序元素一定是前面某个元素的左子结点，且root为前面所有大于该元素的结点中最小的结点

那我们在从右往左遍历时就可以维护一个单调递增的栈，和当前根节点

遇到比栈顶大的元素时，说明是右子结点，直接入栈，

比栈顶小的元素时，说明遇到了左子结点，该左子结点的root的右子树已经遍历完了，开始出栈，更新root记录出栈元素，直到当前元素大于栈顶，此时root为当前元素的根节点，当前元素再入栈继续判断右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool verifyTreeOrder(vector<int> &postorder) {
        stack<int> roots;
        int root = INT_MAX;
        roots.push(root);
        for (int i = postorder.size() - 1; i >= 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            while (!roots.empty() && postorder[i] < roots.top()) {
                root = roots.top();
                roots.pop();
            }
            roots.push(postorder[i]);
        }
        return true;
    }
};