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

#include <climits>
class Solution {
public:
    //对数组进行逆序检测，会按照根节点-》右子树-》左子树 的顺序，并且以此检测是按照，根-》右子树-》右子树根-》右子树，直到遇到小于前一个数的值，即最下层的左子树，
    //数大于后面的数，即它是前一个数的右子树且根节点，若数小于后数，则遇到了左子树，但不知道是谁的左子树，栈维护；
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()){
            return false;
        }
        int root = INT_MAX;
        stack<int> s;
        for(int i=sequence.size()-1; i >= 0; --i){
            if(sequence[i] > root){   
                //左子树却存在大于其根节点的值那么就是不合法的
                return false;
            }
            while(!s.empty() && s.top() > sequence[i]){ //对左子树找它的根节点
                root = s.top();s.pop();
            }
            s.push(sequence[i]);  //存入根节点
        }
        return true;
    }
};