题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
class Solution {
public:
vector<int>v;
bool helper(int head,int tail){
if(head>tail)return true;
if(head==tail)return true;
//只有左子树
if(v[head]<v[tail]&&v[tail-1]<v[tail]){
for(int i=head+1;i<tail-1;i++){
if(v[i]>v[tail])return false;
}
return helper(head,tail-1);
}
//只有右子树
if(v[head]>v[tail]&&v[tail-1]>v[tail]){
for(int i=head+1;i<tail-1;i++){
if(v[i]<v[tail])return false;
}
return helper(head,tail-1);
}
//既有左子树又有右子树
int pos;
for(pos=head;pos<tail;pos++)
if(v[pos]<v[tail]&&v[pos+1]>v[tail])break;
if(pos==tail)return false;
for(int i=head+1;i<=pos;i++)
if(v[i]>v[tail])return false;
for(int i=pos+1;i<tail;i++)
if(v[i]<v[tail])return false;
return helper(head,pos)&&helper(pos+1,tail-1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty())return false;
v=sequence;
return helper(0,v.size()-1);
}
};
查看23道真题和解析