L2-006 树的遍历 （25 分)

时间：2024-01-14 18:25:02

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456

题目：

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

思路：
模板题
代码：
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int maxn=;

int n;

int mid[maxn],po[maxn];

struct node{

    int l,r;

}T[maxn];

int mid_po_build(int la,int ra,int lb,int rb){

    if(la>ra) return ;

    int rt=po[rb];

    int p1=la,p2;

    while(mid[p1]!=rt) p1++;

    p2=p1-la;

    T[rt].l=mid_po_build(la,p1-,lb,lb+p2-);

    T[rt].r=mid_po_build(p1+,ra,lb+p2,rb-);

    return rt;

}

void dfs(int rt){

    queue<int>Q;

    vector<int>v;

    Q.push(rt);

    while(!Q.empty()){

        int w=Q.front();

        Q.pop();

        v.push_back(w);

        if(T[w].l!=) Q.push(T[w].l);

        if(T[w].r!=) Q.push(T[w].r);

    }

    int len=v.size();

    for(int i=;i<len;i++){

        printf("%d%c",v[i],i==(len-)?'\n':' ');

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<n;i++) scanf("%d",&po[i]);

    for(int i=;i<n;i++) scanf("%d",&mid[i]);

    int rt=mid_po_build(,n-,,n-);

    dfs(rt);

    return ;

}

相关文章