题目描述

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式
第一行包含整数 N，表示二叉树的节点数。

第二行包含 N 个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式
输出一行 N 个整数，表示二叉树的层序遍历。

数据范围
1≤N≤30

样例

输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

算法1

(建树) $O(n)$

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

分析：与后序中序转换为前序的代码相仿（无须构造二叉树再进行广度优先搜索～），只不过加一个变量index，表示当前的根结点在二叉树中所对应的下标（从0开始），所以进行一次输出先序的递归过程中，就可以把根结点下标index及所对应的值存储在map[HTML_REMOVED] level中，map是有序的会根据index从小到大自动排序，这样递归完成后level中的值就是层序遍历的顺序～～

如果你不知道如何将后序和中序转换为先序，请看-> https://www.liuchuo.net/archives/2090

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int N = 101, P = 131;

typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

int post[N];
int in[N];
map<int,int>m;

void pre(int root,int start,int end1,int index){
     if(start>end1) return;
     int i = start;
     while(i<end1&&post[root]!=in[i]) i++;
     m[index] = post[root];
     pre(root-(end1-i)-1,start,i-1,2*index+1);
     pre(root-1,i+1,end1,2*index+2);

}


int main() {

    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> post[i];
    for(int i=0; i<n; i++) cin >> in[i];

    pre(n-1,0,n-1,0);
    auto it = m.begin();
    cout << it->second;
    while(++it!=m.end()) cout << " " << it->second;
    return 0;
}