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

• 实际上二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列, 而对后序遍历序列从小到大排序就得到了中序遍历序列

• 我们得到中序遍历序列后, 将其作为入栈序列, 检查后序遍历序列是不是一个合法的出栈序列即可

• 需要以stack作为后续得中间变量

  class Solution {
  public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(!sequence.size()) return false;
        //二叉搜索树的后续遍历从小到大排序就是对应得中序遍历。
        vector<int> inorder(sequence); //复制一个数组
        sort(inorder.begin(), inorder.end());
  
        return IsPopOrder(inorder,sequence);
    }
  
    bool IsPopOrder(vector<int> pushV,vector<int> popV){//分别对应着一种栈得压入，以及栈得探出
        int n = pushV.size();
        stack<int> stk;//准备生成栈用来判断。
  
        int i=0,j=0;//分别指向两个序列当前位置得指针。
        //循环，知道整个序列检查完是不是一一对应
        while(i<n){//1. 要走完全部序列，n在以后要用，所以不能n--;
            stk.push(pushV[i]);//
            while(!stk.empty()&&stk.top()==popV[j]){
                stk.pop();
                j++;
            }
  
            i++;//继续准备下一个压栈
        }
  
        return j == n;
    }
  

};
```