PAT甲级1119.

目录

A1119

题目

样例

样例1

输入:

7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

输出:

Yes
2 1 6 4 7 3 5

样例2

输入:

4
1 2 3 4
2 4 3 1

输出:

No
2 1 3 4

思路和坑点

　　思路：
　　根据先序和后序建树，显然先序和后序不能唯一确定一棵二叉树，所以需要进行判定，然后输出其中可能的情况。因为当某个节点只有一棵子树的时候先序和后序不能确定这棵子树是左子树还是右子树，所以会由多种结果。我们只需要在遇到此种情况下直接修改判定标记即可。可以不用建好树之后再获取中序序列，直接通过先序和后序确定位置关系，再中序中找到位置即可，按照先序+中序建树的思路处理，稍作修改就行，具体看代码实现和注释。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 35
int n;
bool flag=true;                        //是否唯一确定的标记 
int pre[MAXN],post[MAXN],in[MAXN];     //存放序列 
void creat(int prl,int prr,int pol,int por,int st);
int find(int x);                    //在先序中到位置下标 
int main(){        
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d",&n);                    //读入数据 
    for(int i=0;i<n;i++)    scanf("%d",&pre[i]);
    for(int i=0;i<n;i++)    scanf("%d",&post[i]);
    creat(0,n-1,0,n-1,0);            //得到in序列 
    if(flag) puts("Yes");            //判定输出 
    else    puts("No");
    for(int i=0;i<n;i++){
        if(i) putchar(' ');
        printf("%d",in[i]);
    }
    putchar('\n');                    //结尾必须有回车，否则格式错误 
    return 0;    
}
void creat(int prl,int prr,int pol,int por,int st)    //递归填写in序列 
{    
    //prl，prr分别当前子树在先序序列中的左右端点下标
    //pol,por分别是当前字数在后序序列中的左右端点下标
    //st表示当前子树在中序序列中的开始位置 
    int lnum=0,rnum=0;
    if(prl>prr)    return;            //如果序列中没有顶点，返回 
    if(prl==prr) {                    //如果只有一个顶点，在st位置直接填写 
        in[st]=pre[prl];
        return;
    }                                
    int k=find(post[por-1]);            //后序序列的根前一位是子树的根，在此默认为右子树
                                        //找到其在先序中的位置下标 
    lnum=k-prl-1; rnum=prr-k+1;         // 由k计算左右子树的节点个数 
    if((lnum!=0&&rnum==0)||(lnum==0&&rnum!=0)){        //如果该子树只有右子树或者只有左子树，flag为否 
        flag=false;
    }
    int pos=st+lnum;                    //计算根结点在后序序列中的位置 
    in[pos]=pre[prl];                   //填写根结点在后序中 
    creat(prl+1,prl+lnum,pol,pol+lnum-1,pos-lnum);    //递归填写左右子树 
    creat(k,prr,por-rnum,por-1,pos+1);
}
int find(int x)                        //寻找x在先序中的下标位置
{
    for(int i=0;i<n;i++){
        if(pre[i]==x)
            return i;
    }
}