题目描述

已知二叉搜索树得前序遍历序列，判断是否可以构建一棵二叉搜索树

算法1

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int midorder[N],preorder[N],postorder[N];
int n;
int cnt=0;

bool build(int ml,int mr,int pl,int pr,int type){
    if(ml>mr){
        return true;
    }
    int root=preorder[pl];
    int k;
    if(type==0){
        for(k=ml;k<=mr;k++){
            if(midorder[k]==root){
                break;
            }
        }
        if(k>mr){
            return false;
        }
    }else{
        for(k=mr;k>=ml;k--){
            if(midorder[k]==root){
                break;
            }
        }
        if(k<ml){
            return false;
        }
    }

    //递归构建左子树
    if(!build(ml,k-1,pl+1,pl+1+k-1-ml,type)){
        return false;
    }

    //递归构建右子树
    if(!build(k+1,mr,pl+1+k-1-ml+1,pr,type)){
        return false;
    }

    postorder[cnt++]=root;

    return true;
}

int main(){
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>preorder[i];
        midorder[i]=preorder[i];
    }

    //BST中序遍历递增
    sort(midorder,midorder+n);

    if(build(0,n-1,0,n-1,0)){
        cout<<"YES"<<endl;
        //输出后序遍历序列
        for(int i=0;i<n;i++){
            cout<<postorder[i]<<" ";
        }

    }else{
        reverse(midorder,midorder+n);
        cnt=0;
        if(build(0,n-1,0,n-1,1)){
            cout<<"YES"<<endl;
            //输出后序遍历结果
            for(int i=0;i<n;i++){
                cout<<postorder[i]<<" ";
            }
        }else{
            cout<<"NO"<<endl;
        }
    }

    return 0;
}