题目链接:https://www.acwing.com/problem/content/1499/
题目
一个二叉树,树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。
输入格式
第一行包含整数
N
N
N ,表示二叉树的节点数。
第二行包含
N
N
N 个整数,表示二叉树的后序遍历。
第三行包含
N
N
N 个整数,表示二叉树的中序遍历。
输出格式
输出一行
N
N
N 个整数,表示二叉树的层序遍历。
数据范围
1
≤
N
≤
30
1 ≤ N ≤ 30
1≤N≤30,
官方并未给出各节点权值的取值范围,为方便起见,在本网站范围取为
1
∼
N
1∼N
1∼N。
输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2
思路:
中序遍历:
每个点的左边,都是它的左子树
每个点的右边,都是它的右子树
后序遍历:
最后一个点是根节点,
然后根据中序遍历,在后序找到两段
第一段是左子树,第二段是右子树
第一段的最后一个点,就是左子树的根节点
第二段的最后一个点,就是右子树的跟节点
递归处理即可
最后从根节点开始BFS就是层序遍历
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 40;
int n;
int a[N],b[N];
unordered_map<int,int> l,r,pos;
queue<int> que;
int build(int il,int ir,int pl,int pr) // il:先序遍历左端点 ir:先序遍历右端点 pl:后序遍历左端点 pr:后序遍历右端点
{
int root = a[pr];
int k = pos[root];
/*
设后序遍历左子树右端点为x
有 x - pl = ir - il (ir = k - 1)
解得 x = ir - il + pl
即 x = k - 1 - il + pl
后序遍历右子树左端点 = 后序遍历左子树右端点 + 1
后序遍历右子树右端点 = 根节点前一个点 pr - 1
*/
if(il < k) l[root] = build(il, k - 1, pl, k - 1 - il + pl);
if(ir > k) r[root] = build(k + 1, ir, k - 1 - il + pl + 1, pr - 1);
return root;
}
void bfs(int root)
{
que.push(root);
while(que.size())
{
int t = que.front();
que.pop();
if(l.count(t)) que.push(l[t]);
if(r.count(t)) que.push(r[t]);
if(que.size()) cout << t << " ";
else cout << t;
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++)
{
cin >> b[i];
pos[b[i]] = i; // 存中序遍历的位置
}
int root = build(0, n - 1, 0, n - 1);
bfs(root);
return 0;
}