CodingInterview-二叉搜索树的后序遍历序列

验证的方法很简单，由于序列是后序遍历形成，所以序列中的最后一位是根节点，而序列又是二叉搜索树，所以可以根据大于它和小于它将序列分为左右两个子序列。如果验证合理，那么右边子序列的大小一定都是大于根节点的，所以一旦出现反例，就说明验证失败。而它的两个子序列就可以使用递归的方式进行逐一验证，直到序列不可再分。

class Solution {
private:
    vector<int>* sequence;
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int seqSize=(int)(sequence.size());
        if(seqSize==0) return false;
        this->sequence=&sequence;
        return doVerify(0,seqSize-1);
    }
    bool doVerify(int left,int right){
        if(left>=right) return true;
        int middle=(*sequence)[right];
        int split=left;
        while(split<right){
            if((*sequence)[split]>middle) break;
            split++;
        }
        for(int i=split;i<right;i++){
            if((*sequence)[i]<middle) return false;
        }
        return doVerify(left,split-1) && doVerify(split,right-1);
    }
};