[数据结构与算法]树的遍历(bfs)

题目链接:https://www.acwing.com/problem/content/1499/

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

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

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

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

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

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

数据范围
$1\le N\le 30$,
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 $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;
}