20.二叉搜索树的后序遍历

题意：
给定一个数组，判断是不是二叉搜索树的后序遍历
思路：

• 先回忆相关知识点：二叉搜索树的后序遍历的顺序为左右根，结合二叉搜索树的性质可以知道，根节点>左子树上的节点，且<右子树的节点。

1. 根据后序遍历的知识可以知道数组的最后一个元素为根节点
2. 根据二叉搜索树的性质可以知道，除去最后的根节点后，数组可以分为2部分，前一部分所有元素的值小于根节点，后一部分所有元素的值大于根节点
   （这也是本题重要的判定依据）
3. 因为后序遍历是递归结构，所以分割后的两部分数组依然会满足二叉搜索树的后序遍历的顺序
4. 数组的切分可以通过设置索引进行标记来实现

• 设计思路：
  根据以上思路，本题的设计重点在于递归判断一下分割后的数组是否满足二叉搜索树后序遍历的性质。即第2点。
• 代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> s) {
        int n=s.size();
        if(n==0)
            return false;
        if(n==1)
            return true;
        return isBST(s,0,n-1);
        
    };
    bool isBST(vector<int> &s,int first,int last){
        
        if(last<=first)
            return true;
        int cutIdx=first,root=s[last];
        while(cutIdx<last && s[cutIdx]<root)
            cutIdx++;
        for(int i=cutIdx;i<last;i++)
            if(root>s[i])
                return false;
        return isBST(s,first,cutIdx-1)&&isBST(s,cutIdx,last-1);
    }
};