题目描述

(1)比较preorder[l1+1]与postorder[r2-1]是否相等，如果相等，说明可能是左子树也可能是右子树，不唯一
如果preorder[l1+1]!=postorder[r2-1]说明preorder[l1+1]为左子树的根节点，postorder[r2-1]为右子树的根节点
直到左右子树的根节点之后，就可以分别确定左子树和右子树的前序和后序序列
(2)枚举左子树的长度

算法1

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=35;
int preorder[N],postorder[N],midorder[N];
int l[N],r[N];
int n;

int cnt = 0;


bool is_only=true;

int build(int l1,int r1,int l2,int r2){

    int root=preorder[l1];

    if(l1==r1||l2==r2){
        return root;
    }

    if(preorder[l1+1]==postorder[r2-1]){
        //不确定，方案不唯一
        l[root]=build(l1+1,r1,l2,r2-1);
        is_only=false;
    }else{
        //递归构建左右子树
        int j,k;
        for(j=l1+1;j<=r1;j++){
            if(preorder[j]==postorder[r2-1]){
                break;
            }
        }
        for(k=r2-1;k>=l2;k--){
            if(postorder[k]==preorder[l1+1]){
                break;
            }
        }

        l[root]=build(l1+1,j-1,l2,k);
        r[root]=build(j,r1,k+1,r2-1);


    }

    return root;
}

void trave(int root){
    if(!root){
        return ;
    }
    if(l[root]){
        trave(l[root]);
    }
    midorder[cnt++]=root;
    if(r[root]){
        trave(r[root]);
    }
}


int main(){
    cin>>n;

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

    int root=build(0,n-1,0,n-1);

    //根据根节点打印
    if(is_only){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    trave(root);

    cout<<midorder[0];
    for(int i=1;i<cnt;i++){
        cout<<" "<<midorder[i];
    }

    return 0;
}

算法2

枚举左子树的长度，也就确定了右子树的长度，枚举之后进行二叉树的构建，记录左右子树的构建方案数
每次枚举都对计数的总方案数比较，如果方案数大于1，直接返回，记录中序序列

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=35;
int preorder[N],postorder[N];
int n;

int build(int l1,int r1,int l2,int r2,string& in){

    if(l1>r1||l2>r2){
        return 1;
    }
    if(preorder[l1]!=postorder[r2]){
        return 0;
    }

    int res=0;
    //枚举每一个左子树的长度
    for(int i=l1;i<=r1;i++){
        string lin,rin;
        //递归构建左子树
        int cnt1=build(l1+1,i,l2,l2+i-l1-1,lin);
        //递归构建右子树
        int cnt2=build(i+1,r1,l2+i-l1,r2-1,rin);
        //cnt1,cnt2分别表示左右子树的方案数
        if(cnt1&&cnt2){
            in=lin+to_string(preorder[l1])+" "+rin;//输出字符之间空格
            res+=cnt1*cnt2;
            if(res>1){
                break;
            }
        }

    }
    return res;
}

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

    for(int i=0;i<n;i++){
        cin>>postorder[i];
    }
    string in;
    //根据构建的树是否唯一输出
    int res=build(0,n-1,0,n-1,in);
    if(res>1){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }

    //输出树的中序序列
    if(in.size()){
        in.pop_back();
        cout<<in<<endl;;
    }

    return 0;
}