[C++知识库]AcWing 46. 二叉搜索树的后序遍历序列（C++）- 二叉搜索树遍历

题目链接：https://www.acwing.com/problem/content/description/44/
题目如下：

class Solution {
public:
    
    vector<int> seq;
    
    bool verifySequenceOfBST(vector<int> sequence) {
        //直接从二叉树的后序遍历构造树，构造不出来则返回false
        //后序遍历的顺序：左右根，即最后一个元素一定是整棵树的根节点
        //二叉搜索树的特点：中序遍历是有序的（左根右）
        seq=sequence;
        return dfs(0,seq.size()-1);
    }
    
    bool dfs(int l,int r){
        if(l>=r) return true;
        int root=seq[r];//最后一个元素为当前树的根节点
        
        int mid=l;
        while(mid<r&&seq[mid]<root) mid++;//从最左边的一个元素开始算起，找到第一个>=root的节点为止
        
        for(int i=mid;i<r;i++){//遍历树的右半部分，要确保这右半部分全部大于root
            if(seq[i]<root) return false;
        }
        
        return dfs(l,mid-1)&&dfs(mid,r-1);//注意！！！中间的mid位置不能省，最后一个根节点可以扔掉
        
    }
};