二叉搜索树的后序遍历序列
二叉搜索树的后序遍历序列
http://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int len=sequence.size();//获取向量的长度
if(len==0)
return false;
if(len==1)
return true;
return ju(sequence,0,len-1);
}
protected:
bool ju(vector<int> a, int start,int end)
{ if(start>=end) //递归终止条件
return true;
int tem=a.back();
int i=end;
while(i>start && a[i-1]>tem)//判断右子树是否满足
i--;
int j;
for(j=start;j<i;j++)//判断左子树是否满足
if(a[j]>tem)
return false;
return ju(a,start,i-1) && ju(a,i,end-1); //新的左右子树继续判断
}
};</int></int>