class Solution {

public:

    bool isBST(vector<int> sequence, int left, int right)

    {

        if(left >= right) //left==right对应的是叶子结点，left>right对应空树

        {

            return true;

        }

        int check_right = right;

        //找右子树，tmp为右子树最左分界点

        while((check_right > left) && (sequence[check_right - 1] > sequence[right]) )

        {

            --check_right;

        }

        //找左子树

        for(int check_left = check_right - 1; check_left >= left; --check_left)

        {

            if(sequence[check_left] > sequence[right])

            {

                return false;

            }

        }

        return (isBST(sequence, left, check_right - 1) && isBST(sequence, check_right, right - 1));

    }

    bool VerifySquenceOfBST(vector<int> sequence) {

        //{5,7,6,9,11,10,8}

        if(sequence.empty())

        {

            return false;

        }

        return isBST(sequence, 0, sequence.size() - 1);

    }

};