题解 | #二叉搜索树的后序遍历序列#

class Solution {
  public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        // 处理序列为空情况
        if (sequence.size() == 0) return false;

        stack<int> s;
        int root = INT_MAX;
        // 以根，右子树，左子树顺序遍历
        for (int i = sequence.size() - 1; i >= 0; i--) {
            // 确定根后一定是在右子树节点都遍历完了，因此当前sequence未遍历的节点中只含左子树，左子树的节点如果>root则说明违背二叉搜索的性质
            if (sequence[i] > root) return false;
            // 进入左子树的契机就是sequence[i]的值小于前一项的时候，这时可以确定root
            while (!s.empty() && s.top() > sequence[i]) {
                root = s.top();
                s.pop();
            }
            // 每个数字都要进一次栈
            s.push(sequence[i]);
        }
        return true;
    }
};