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

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        queue<int> que;  
        for(auto x : sequence) que.push(x);  //队列记录当前sequence的值
        sort(sequence.begin(),sequence.end());   //从小到大排序，形成中序遍历序列
        stack<int> sta;   //利用栈判断结果，中序遍历的进栈以某种方式出栈一定可以形成后序遍历序列
        int i = 0;
        while(i <= sequence.size()){
            if(sta.size() == 0 && que.size() == 0) return true;  //都空了表示成功
            if(i == sequence.size()) return false;  //i超过了序列数，此时如果栈队不空则说明不行
            sta.push(sequence[i]);
            while(sta.top() == que.front()){  //栈顶和队头相等，出栈出队，表示本次后序和中序可以转换
                sta.pop();
                que.pop();
                if(sta.size() == 0) break;   //直到栈空或者二者不等结束
            }
            i++;
        }
        return false;
    }
};