剑指23：二叉搜索树的后序遍历序列
二叉搜索树的后序遍历序列
http://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd
二叉搜索树的特点：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
后序遍历的特点：遍历顺序左右根，因此根节点位于当前序列的末尾，小于根结点的值为左子树上节点，大于根结点的值为右子树上节点
关键点：找出左右子树的序列范围进行递归
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty())
return false;
return VerifySqu(sequence,0,sequence.size());
}
bool VerifySqu(vector<int> sequence,int st,int et){
if(st>=et)
return true;
int guard=sequence[et];
int i=st;
for(;i<et;i++){
if(sequence[i]>guard)
break;
}
for(int j=i;j<et;j++){
if(sequence[j]<guard)
return false;
}
return VerifySqu(sequence,st,i-1)&&VerifySqu(sequence,i,et-1);
}
};
查看30道真题和解析