方法一：

分治+递归

思路： 二叉树的后序遍历顺序是：左子树 -> 右子树 -> 根节点 因此序列的最后一个数代表了根节点 因此我们可以将一个序列划分为3段, 左子树+右子树+根, 例如[4, 8, 6, 12, 16, 14, 10]可以根据根节点的值将其划分为左子树[4, 8, 6], 右子树[12, 16, 14], 根[10], 由于我们是先确定的右子树区间, 因此当左子树区间中出现大于根节点的值时, 序列不合法, 我们再采用分治的思想, 对于每段序列代表的子树, 检查它的左子树和右子树, 当且仅当左右子树都合法时返回true

代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
       int n=sequence.size();
       //如果是空树，题目约定空树不是二叉搜索树
       if(n==0) return false;
       //后序：左右根（分治思想）+递归（后序遍历和二叉搜索树的递归定义）
       return devide(sequence,0,n-1);
    }
    //分治+递归
    bool devide(vector<int>&a,int l,int r){
        //递归的结束条件：如果这棵树只剩下一个节点，就返回true
        if(l>=r) {
            return true;
        }
        //划分区间的最后一个节点为根节点
        int root=a[r];
        //划分右子树:由于如果该树是二叉搜索树，则右树的节点的值大于根节点的值
        int j=r-1;
        while(j>=0&&a[j]>root) j--;
        //剩下的就是左子树，如果左子树中有节点的值大于根节点的值，那么就不是二叉搜索树
        int i=l;
        for(i=l;i<=j;i++){
            if(a[i]>root){
                return false;
            }
        }
        //由于二叉搜素树的递归定义，所以需要判断一下左右子树是否为二叉搜索树
        return devide(a,l,j)&&devide(a,j+1,r-1);
    }
};

方法二：

二叉搜索树对应的中序遍历是升序 中序：入栈，后序：某一种出栈顺序

思路：实际上二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列, 而对后序遍历序列从小到大排序就得到了中序遍历序列 我们得到中序遍历序列后, 将其作为入栈序列, 检查后序遍历序列是不是一个合法的出栈序列即可 对于检查栈的合法压入、弹出序列问题, 请看栈的压入、弹出序列题解

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
      int n=sequence.size();
      //特判一下，题目约定空树不是二叉搜索树
      if(n==0) return false;
      //由于如果是二叉搜索树，那么其中序遍历是升序的
      vector<int> inorder(sequence);
      sort(inorder.begin(),inorder.end());
      return outorder(inorder,sequence);
    }
    //再将中序遍历压入栈中，看一下有没有满足后序的出栈顺序
    bool outorder(vector<int>inorder,vector<int>sequence){
        stack<int> stack1;
        int j=0;
        //遍历中序，将其对应的元素一个一个依次入栈
        //每入栈一个元素，就判断一下如果当前栈非空且栈顶元素与后序的元素对应，就出栈，并j++
        for(int i=0;i<inorder.size();i++){
             stack1.push(inorder[i]);
             while(!stack1.empty()&&stack1.top()==sequence[j]){
                j++;
                stack1.pop();
             }
        }
        //如果j==sequence.size(),就表明存在一种出栈顺序和后序遍历一致
        return j==sequence.size();
    }
};