class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.size() <= 0)
return false;
int size = sequence.size();
return IsSe(sequence, 0, size - 1);
}
bool IsSe(vector<int>s, int start, int end)
{
if ( (end - start) <= 0)
return true;
int rootVal = s[end];
int i = start;
for (; i <= end - 1; ++i)
{
if (rootVal>s[i])
break;
}
int j = i;
for (; j <= end - 1; ++j)
{
if (s[j]<rootVal)
return false;
}
bool left = false;
bool right = false;
if(i>0)
left = IsSe(s, start, i);
if(i<end)
right = IsSe(s, i + 1, end - 1);
return (left&&right);
}
};