二叉搜索树的后序遍历序列：最直观的想法是，根据二叉树的特性，左<中<右，根据后序遍历的顺序，左-右-中，可以得知，每次根据区间的最后一个节点将区间分为左子区间和右子区间两个部分，并且判断是否左子区间的值均小于最后一个节点且右子区间的值均大于最后一个节点，如此循环往复直至区间只剩下一个元素为止则返回。

bool dfs(vector<int> &sequence,int l,int r)
{
   if(l>=r) //区间为空或者只有一个元素则为真
     return true;
   int root=sequence[r]; //中间节点
   int index; //分界点
   for(int i=l;i<r;i++)  //寻找分界点
   {
       if(sequence[i]>root)
       {
           index=i;
           break;
       }
   }
   for(int i=l;i<index;i++) //判断左子区间
   {
       if(sequence[i]>root) //一旦大于返回false
           return false;
   }
   for(int i=index;i<r;i++) //判断右子区间
   {
       if(sequence[i]<root) //一旦小于返回false
           return false;
   }
   //满足条件为左右区间均满足
   return dfs(sequence,l,index-1)&&dfs(sequence,index,r-1);
}
bool VerifySquenceOfBST(vector<int> sequence) 
{
     int n=sequence.size(); //二叉搜索树大小
     if(n==0) //空树不是二叉搜索树
        return false;
     return dfs(sequence,0,n-1); //深度优先遍历
}

idea：后序遍历顺序是左-右-根，逆序后序遍历顺序则是根-右-左，其中根节点是左子树的上限，根节点是右子树的下限。每一个节点都会入栈，如果当前节点大于上一个元素，则表明该节点是上一个元素的右孩子，反之如果当前节点小于上一个元素，则表明当前元素是某一个祖辈节点的左孩子，这时候我们需要找到该祖辈节点并且将该祖辈节点以及其右子树全部弹出栈，该祖辈节点的值将会成为新的上限，此时右子树均已经出栈了，剩下的只有左子树了，如果左子树节点大于新的上限则表明不满足条件，由于root表示上限，故root初始化为最大值INT_MAX。（单调栈思想很难想所以先模仿一回生二回熟）

bool VerifySquenceOfBST(vector<int> sequence) 
{
    int n=sequence.size(); //二叉搜索树大小
    if(n==0) //空树不是二叉搜索树
      return false;
    int root=INT_MAX; //初始化为最大值
    stack<int> st;
    for(int i=n-1;i>=0;i--) //逆序遍历
    {
       //当到达root即为右子树都判断完了只剩下左子树了
       //如果左子树大于根节点则不满足条件
       if(sequence[i]>root)
          return false;
       //如果栈不为空且栈顶元素大于当前序列元素则表明达到左子树部分
       while(!st.empty()&&st.top()>sequence[i])
       {
           //root一定是二叉树或者某个二叉子树的根节点
           root=st.top();
           //并且它的右子树节点都出栈了即只剩下左子树了
           st.pop();
           //以第三个示例为例 当到达6的时候 由于在9的下一个 
           //故不知道下一个是不是9的左右 这时root是10
       }
       //每一个元素都要进栈
       st.push(sequence[i]);
     }
     return true;
}