题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
//递归 的做法
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0) return false;
if(sequence.size()==1) return true;
int index=0;
int last=sequence[sequence.size()-1];
vector<int> left;
while(sequence[index]<last){
left.push_back(sequence[index]);
index++;
}//index为右子树第一个数的位置
int midpos=index;
vector<int> right;
while(sequence[index]>last){
right.push_back(sequence[index]);
index++;
}
if(index!=sequence.size()-1) return false;//没有成功划分
else{
if(left.size()!=0&&right.size()!=0)
return VerifySquenceOfBST(left)&&VerifySquenceOfBST(right);
else if(left.size()!=0) return VerifySquenceOfBST(left);
else return VerifySquenceOfBST(right);
}
}
};
