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

class Solution {
public:
    //由给定数组判断是不是二叉搜索树的后序遍历可以这样做
    //首先最后一个值肯定是树的根节点，根据这个值的大小把前面的数组分为左子树部分和右子树部分
    //然后左子树的所有值必须小于这个值，右子树的所有值必须大于这个值，如果出现反例则直接返回false
    bool f(vector<int> sequence,int start, int end){
        if(start>=end){//子树为空树或者只有一个节点的子树直接返回true
            return true;
        }
        int root=sequence[end];//取最后一个值
        //根据这个值的大小把数组分成左子树数组和右子树数组
        int i=start;
        for(i=start;i<end;i++){
            if(sequence[i]>root){//说明从i开始往后的数组部分是属于右子树数组部分
                break;
            }
        }
        //然后根据分出来的左右子树数组来判断是否满足二叉搜索树的特点
        //这里有个优化细节，不用判断左子树数组了，因为左子树数组一定满足，只需要判断右子树数组即可
        for(int index=i+1;index<end;index++){
            if(sequence[index]<=root){//右子树数组应该全部大于root才对，此时直接返回false
                return false;
            }
        }
        return f(sequence, start,i-1)&&f(sequence, i, end-1);
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {

        
        if(sequence.size()==0){//空树约定不是二叉搜索树
            return false;
            
        }
        if(sequence.size()==1){//只有一个节点的二叉树一定是二叉搜索树
            return true;
        }
        
        return f(sequence, 0, sequence.size()-1);
        
        
    }
};