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

第十七题

后续遍历将树分隔开来 左右子树递归调用 判断是否符合要求

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0)
            return false;
        // 因为后序遍历 所以容器的最后一个值 就是根节点
        // 前面利用上面说的 根节点 分为两段 （左边一段全小于根，右边一段全大于根）
        
        // 再把前后两段递归调用函数
        // middle 就是用来区分左右两段的根节点 获得值后 pop掉
        int middle = sequence.back();
        sequence.pop_back();
        
        // 这里循环只用于 计算左边小于根节点的个数
        // 这里不用判断是否这个值 会有大于根的值，因为判断条件就是小的
        // 要判断是否在后面会出现太小的值 在第二个循环中向后判断
        int left_length=0;
        for(int i =0;i<sequence.size();i++)
        {
            if(sequence[i]<=middle)
                left_length++;
            else
                break;
        }
        // 计算右边大于根节点的个数
        int right_length=sequence.size()-left_length;
        
        // 向后循环，检查是否有太小的值，因为要求是在left_length后面的值都是大的值
        for(int i =left_length;i<sequence.size();i++)
        {
            // 如果后面还有比middle小的 则肯定错
            if(sequence[i]<middle)
                return false;
        }
        
        // 保留返回的ans
        bool ans=true;
        // 如果左边长度为0 显然就不用统计了
        if(left_length!=0){
            // 递归调用函数 将左半边作为参数直接传入
            // 相当于将左子树全部传入判断 左子树出错 则说明肯定出错
            // 判断方法 递归
            ans=VerifySquenceOfBST(vector<int>(sequence.begin(),sequence.begin()+left_length));
        }
        // ans有false 立马就可以判断出结果是错的
        if(ans==false)
            return false;
        
        // 右半部分 同上 判断右子树
        if(right_length!=0){
            ans=VerifySquenceOfBST(vector<int>(sequence.begin()+left_length,sequence.end()));
        }
        return ans;
    }
};