题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
#include <iostream>
#include <vector>
using namespace std;
void bstTree(vector<int> &sequence,int start,int end,bool &m){
if(start<end){
int p=end;
for(int i=start;i<=end;i++){
if(sequence[i]>sequence[end]){
p=i;
break;
}
}
for(int i=p+1;i<=end;i++){
if(sequence[i]<sequence[end]){
m=false;
break;
}
}
bstTree(sequence,start,p-1,m);
bstTree(sequence,p,end-1,m);
}
}
bool VerifySquenceOfBST(vector<int> sequence){
if(sequence.size()==0)
return 0;
else{
bool m=true;
bstTree(sequence,0,sequence.size()-1,m);
return m;
}
}
int main(){
int a[7]={5,7,6,9,11,10,8};
vector<int> vec(a,a+7);
cout<<VerifySquenceOfBST(vec)<<endl;
system("pause");
}
思路：
已知条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。
1、确定root；
2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；
3、遍历右子树，若发现有小于root的值，则直接返回false；
4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。