二叉搜索树的后序遍历

class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int n = sequence.size();
if(!n)
return false;
return isLastOrder(sequence, 0, n-1);
}
private:
bool isLastOrder(vector<int> seq, int start, int end)
{
if(start >= end)
return true;
int last = seq[end]; //最后一个元素,也就是根结点
int i = start;
while(i< end && seq[i] < last)
i++;//循环结束时，有 seq[i] > last,即i为第一个大于last的元素的下标
//或者时 i>end 了，即所有的元素都小于last
//注意，[start, i-1]都比last小，此时我们还需要判断[i, end-1]是否都比last大
for(;i<end; i++)
{
if(seq[i] > last)
;
else
return false;
}
return isLastOrder(seq, start, i-1) && isLastOrder(seq, i, end-1);
}
};</int></int>