PAT 2020秋季考试第三题

解题思路

首先根据中序遍历和先序遍历构建一棵二叉树。然后层次遍历，每次取层次遍历的第一个值打印即可！！可以在构建树的时候加一个layer表示树所在的层，然后层次遍历时如果是同一层就只打印第一个即可。

代码

#include <cstdio>
#include <queue>
using namespace std;
const int maxn=30;
int n,in[maxn],pre[maxn];
struct Node{
    int v,layer;
    Node* left,*right;
    Node(int v=0,int layer=1,Node* l=NULL,Node* r=NULL):v(v),layer(layer),left(l),right(r){}
};
Node* root;
void build(Node*& r,int l1,int r1,int l2,int r2,int layer){//l1-->pre,l2-->in
    if(l1>r1||l2>r2) return;

    r=new Node(pre[l1]);//先序遍历第一个为根节点
    r->layer=layer;
    //在中序中找到跟
    int p=l2;
    while (p<r2){
        if(in[p]==pre[l1]) break;
        p++;
    }
    //pre中左右的个数
    int lnum=p-l2;
    int rnum=r2-p;
    build(r->left,l1+1,l1+lnum,l2,p-1,layer+1);
    build(r->right,r1-rnum+1,r1,p+1,r2,layer+1);
}
int k=0;
void print(Node* r){
    queue<Node*> q;
    q.push(r);
    int layer=0;
    while (!q.empty()){
        k++;
        Node* node=q.front();
        q.pop();
        if(node->layer!=layer){
            layer=node->layer;
            printf("%d",node->v);
            if(k<n) printf(" ");
        }
        if(node->left) q.push(node->left);
        if(node->right) q.push(node->right);
    }
}


int main(){
    scanf("%d",&n);

    for(int i=0;i<n;i++) {
        scanf("%d",&in[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%d",&pre[i]);
    }
    build(root,0,n-1,0,n-1,1);
    print(root);

    return 0;
}