class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
            return false;
        int length=sequence.size();
        //获取后续遍历的最后一个数，是二叉搜索树的最后一个元素
        int root=sequence[length-1];
        vector<int> left,right;//左右子树
        int i=0;
        for(;i<length-1;i++)
        {
            //左子树元素小于根节点
            if(sequence[i]>root)
                break;
            left.push_back(sequence[i]);
        }
        int j=i;
        for(;j<length-1;j++)
        {
            if(sequence[j]<root)
                return false;
            right.push_back(sequence[j]);
        }
        //判断左子树
        bool aleft=true;
        if(i>0)
            aleft=VerifySquenceOfBST(left);
        bool aright=true;
        if(i<length-1)
            aright=VerifySquenceOfBST(right);
        return (aleft&&aright);
    }
};