题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

题解

二叉搜索树：根节点的左子树节点都小于根节点；右子树节点都大于根节点。

后序遍历：左 | 右 | 根

递归

class Solution {
    bool verifyPostorder(vector<int>& postorder, int left, int right) {
        if (left >= right) return true;
        int root = postorder[right];
        int mid = left;
        while (mid < right && postorder[mid] < root) mid++;
        for (int i = mid; i < right; i++) {
            if (postorder[i] < root) return false;
        }
        return verifyPostorder(postorder, left, mid - 1) 
        && verifyPostorder(postorder, mid, right - 1);
    }
public:
    bool verifyPostorder(vector<int>& postorder) {
        return verifyPostorder(postorder, 0, postorder.size() - 1);
    }
};

时间复杂度 $O(N^2)$ ：每次递归减去一个根节点，递归 O(N)；最坏情况下，树退化为链表，每次递归都需要遍历剩余所有节点，O(N)。
空间复杂度 $O(N)$ ：最差情况下，当树退化为链表，递归深度为 O(N)。

单调栈

后序遍历的逆序：根 | 右 | 左，其中 根 | 右 递增，依次入栈；

当 左 开始入栈时，比栈顶小，开始出栈，直到栈顶元素比将要入栈的元素小或栈为空；

最后一个出栈的即为根节点，后面入栈的节点都在根节点的左子树，应该都比记录的根节点小。

根节点初始值设为 INT_MAX。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int n = postorder.size();
        stack<int> stk;
        int root = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            if (postorder[i] > root) return false;
            while (!stk.empty() && postorder[i] < stk.top()) {
                root = stk.top(); stk.pop();
            }
            stk.push(postorder[i]);
        }
        return true;
    }
};