题目描述
一个二叉树,树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。
输入格式
第一行包含整数 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
时间复杂度 O(n)
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 100;
int n, a[N], b[N], c[N];
vector<int> level[N];
void build(int al, int ar, int bl, int br, int d) // al、ar代表当前子树中序遍历左右端点, bl、br代表后序左右端点, d代表当前根结点深度
{
if(al > ar) return;
int k = b[br]; // 取根结点
level[d].push_back(k); // 根结点加入当前层
build(al, c[k] - 1, bl, bl + c[k] - 1 - al, d + 1); // 递归左子树
build(c[k] + 1, ar, bl + c[k] - al, br - 1, d + 1); // 递归右子树
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
{
scanf("%d",&b[i]);
}
for(int i = 1; i <= n; i ++)
{
scanf("%d",&a[i]);
c[a[i]] = i;
}
build(1, n, 1, n, 0);
for(int i = 0; i < n; i ++)
{
for(int x : level[i]) printf("%d ", x);
}
return 0;
}