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

class Solution {
public:
    vector<int>v;
    bool helper(int head,int tail){
        if(head>tail)return true;
        if(head==tail)return true;
        
        //只有左子树
        if(v[head]<v[tail]&&v[tail-1]<v[tail]){
            for(int i=head+1;i<tail-1;i++){
                if(v[i]>v[tail])return false;
            }
            return helper(head,tail-1);
        }
        //只有右子树
        if(v[head]>v[tail]&&v[tail-1]>v[tail]){
            for(int i=head+1;i<tail-1;i++){
                if(v[i]<v[tail])return false;
            }
            return helper(head,tail-1);
        }
        //既有左子树又有右子树
        int pos;
        for(pos=head;pos<tail;pos++)
            if(v[pos]<v[tail]&&v[pos+1]>v[tail])break;
        if(pos==tail)return false;
        for(int i=head+1;i<=pos;i++)
            if(v[i]>v[tail])return false;
        for(int i=pos+1;i<tail;i++)
            if(v[i]<v[tail])return false;
        return helper(head,pos)&&helper(pos+1,tail-1);
        
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())return false;
        v=sequence;
        return helper(0,v.size()-1);
    }
};