//递归 的做法

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0) return false;
        if(sequence.size()==1) return true;
        int index=0;
        int last=sequence[sequence.size()-1];
        vector<int> left;
        while(sequence[index]<last){
            left.push_back(sequence[index]);
            index++;
        }//index为右子树第一个数的位置
        int midpos=index;
        vector<int> right;
        while(sequence[index]>last){
            right.push_back(sequence[index]);
            index++;            
        }
        if(index!=sequence.size()-1) return false;//没有成功划分
        else{
            if(left.size()!=0&&right.size()!=0)
                return VerifySquenceOfBST(left)&&VerifySquenceOfBST(right);
            else if(left.size()!=0) return VerifySquenceOfBST(left);
            else return VerifySquenceOfBST(right);
        }
    }
};