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

#include <climits>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        //辅助遍历,null
      if(sequence.size()==0) return false;
      stack<int> s;
      //根节点的根节点无限大
      int root = INT_MAX;
        //for循环，以根->右->左的形式进行循环
      for(int i = sequence.size()-1; i >=0; i--)
      {
        //判断是否为搜索二叉树，二叉树的性质是左值<根植<右值
        if(sequence[i]>root)return false;
        //当遇到s.top()>sequence[i]时，就说明所有右子树的节点以遍历完全，此时的sequence[i]就是左子树的起始节点
       while(!s.empty()&&s.top()>sequence[i])
       {
        //把所有右子树的节点都从stack弹出时，依然满足true的状态就说明该列表是所要求的结果，最后一个s.top()是根节点
        root = s.top();
        s.pop();
       }
       s.push(sequence[i]);
      }
      return true;
     
    }
};