JZ33 二叉排序树的后序遍历序列

class Solution {
public:
    //判断该数组是不是某二叉搜索树的后序遍历的结果。
    //如果是则返回 true ,否则返回 false 
    //注意传入参数是一个int类型的vector容器

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) 	//二叉树为空，则返回flase
            return false;
        return VerifyCore(sequence, 0, sequence.size()-1);

    }
	//参数：（后序序列，遍历范围左端，遍历范围右端）
    bool VerifyCore(vector<int> &s, int l, int r)
    {
        if(l >= r) 			//递归结束条件：序列中的值都被遍历完了，也就是从l到r都遍历完了
            return true;
        
        int root = s[r];	//找到根节点

        int i = l;			
        for( ; i<r; i++)	//遍历左子树，找到第一个比根大的节点，后边的都是右子树
        {
            if(s[i] > root)
                break;
        }
        for(int j = i; j< r;j++)	//遍历右子树，看右子树中是否有比根小的节点，若有，则不是后序遍历序列
        {
            if(s[j]<root)
                return false;
        }
		
        //返回值是左子树和右子树都满足排序二叉树的条件才可以！
        return VerifyCore(s, l, i-1) && VerifyCore(s, i, r-1);
    }

};