PAT甲级1127.

目录

A1127

题目

样例

输入:

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

输出:

1 11 5 8 17 12 20 15

思路和坑点

　　思路：
　　先使用中序和后序序列递归建树，然后对建成的树进行层序遍历并保存层序遍历的结果，统计每一层的节点数量，然后对偶数层的节点序列进行逆转，就是最后需要的输出序列。

AC代码

#include<bits/stdc++.h>
using namespace std; 
typedef struct node{                //二叉树的结点定义
    int data;
    struct node *left,*right;
}Node,*Tree;
int n;
int post[31];                       //后序遍历序列
int in[31];                         //中序遍历序列
int layercnt[31]={0};               //统计每层的元素个数
vector<int> layer;                  //存放层序遍历序列
Node *creat(int pl,int pr,int il,int ir);//由中序和后序建树的函数
int layorder(Tree root);            //层序遍历
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d",&n);                 //读入序列
    for(int i=0;i<n;i++)
        scanf("%d",&in[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&post[i]);
    Tree root=creat(0,n-1,0,n-1);   //建树
    int layern=layorder(root);      //层序遍历，并返回最大的层数
    int sum=1;                      //已经处理过的结点个数，根不需要处理，直接跳过，所以初始化为1
    for(int i=1;i<=layern;i++){     //偶数层进行反转
        if(i%2==0)                  
            reverse(layer.begin()+sum,layer.begin()+sum+layercnt[i]);
        sum+=layercnt[i];           //累加处理过的结点个数
    }
    for(int i=0;i<layer.size();i++){//输出最终的序列
        if(i) putchar(' ');
        printf("%d",layer[i]);
    }
    return 0;    
}
Node *creat(int pl,int pr,int il,int ir)
{
    if(pl>pr) return NULL;
    Node *root=new node;
    root->data=post[pr];
    int k;
    for(k=il;k<=ir;k++){
        if(in[k]==post[pr])    break;
    }
    int leftnum=k-il;
    root->left=creat(pl,pl+leftnum-1,il,k-1);
    root->right=creat(pl+leftnum,pr-1,k+1,ir);
    return root;
}
int layorder(Tree root)
{
    int maxlayer=0,cnt=0;                       //maxlayer记录层数，cnt记录每一个层的元素个数
    queue<Node*> q;
    Node * last=root,*tail=root;                //last记录当前层的最后一个，tial记录下一层的最后一个位置
    q.push(root);
    while(!q.empty()){
        Node * now=q.front();
        q.pop();
        layer.push_back(now->data);             //加入层序遍历序列
        cnt++;
        if(now->left) q.push(tail=now->left);   //孩子入队并更新tail
        if(now->right) q.push(tail=now->right);
        if(now==last){                          //如果当前层已经处理完毕
            layercnt[maxlayer++]=cnt;           //统计当前层节点数量，并重置计数器
            cnt=0;
            last=tail;                          //更新last
        }    
    }
    return maxlayer;                            //返回树的最大层数
}