AcWing 1497. 树的遍历

【题目描述】
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

【输入格式】
第一行包含整数N ，表示二叉树的节点数。
第二行包含N 个整数，表示二叉树的后序遍历。
第三行包含N 个整数，表示二叉树的中序遍历。

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

【数据范围】
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

思路

给出后序遍历和中序遍历的结果，就可以构造出这棵树，有了数的结构，可以使用队列进行层序遍历

代码

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;
const int N = 32;
int postorder[N],inorder[N];
unordered_map<int,int> l,r,pos;

vector<int> res;
//args(中序遍历左边界，中序遍历右边界，后续遍历左边界，后序遍历右边界)
int build(int il,int ir,int pl,int pr)
{
　　 //后续遍历的最后一个就是根节点
    int root = postorder[pr];
　　 //得到这一点的位置
    int k = pos[root];
　　 //建左树
    if (il < k) l[root] = build(il,k-1,pl,pl+k-1-il);
　　 //建右树
　　 if (ir > k) r[root] = build(k+1,ir,pl+k-il,pr-1);
   
    return root;
}
void bfs(int root)
{
    queue<int> q;
    q.push(root);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        cout << t << " ";
　　　　 //有左子树，就加入左子树的根节点
        if (l.count(t))
            q.push(l[t]);
　　　　 //有右子树，就加入右子树的根节点
        if (r.count(t))
            q.push(r[t]);
    }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) cin >> postorder[i];
    for(int j = 0;j < n;j++) 
    {
        cin >> inorder[j];
        //记录这一点的位置，方便找
        pos[inorder[j]] = j; 
    }
　　 //建树
    int root = build(0,n-1,0,n-1);
    bfs(root);
    return 0;
}