title: acwing1497-树的遍历
tags:

  • ACM
  • 树
  • acwing
    abbrlink: a9cc3b0f
    date: 2021-03-27 12:24:52

题目

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

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

输入格式

第一行包含整数 NN，表示二叉树的节点数。

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

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

输出格式

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

数据范围

1≤N≤301≤N≤30

输入样例：

  1. 7
  2. 2 3 1 5 7 6 4
  3. 1 2 3 4 5 6 7

输出样例：

  1. 4 1 6 3 5 7 2

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #include <queue>
  7. using namespace std;
  9. const int N = 40;
  11. int n;
  12. int postorder[N], inorder[N];
  13. unordered_map<int, int> l, r, pos;
  15. int build(int il, int ir, int pl, int pr)
  16. {
  17.     int root = postorder[pr];
  18.     int k = pos[root];
  19.     if (il < k) l[root] = build(il, k - 1, pl, pl + k - 1 - il);
  20.     if (ir > k) r[root] = build(k + 1, ir, pl + k - 1 - il + 1, pr - 1);
  21.     return root;
  22. }
  24. void bfs(int root)
  25. {
  26.     queue<int> q;
  27.     q.push(root);
  28.     while (q.size())
  29.     {
  30.         auto t = q.front();
  31.         q.pop();
  32.         cout << t << ' ';
  33.         if (l.count(t)) q.push(l[t]);
  34.         if (r.count(t)) q.push(r[t]);
  35.     }
  36. }
  39. int main()
  40. {
  41.     cin >> n;
  42.     for (int i = 0; i < n; i ++ ) cin >> postorder[i];
  43.     for (int i = 0; i < n; i ++ )
  44.     {
  45.         cin >> inorder[i];
  46.         pos[inorder[i]] = i;
  47.     }
  48.     int root = build(0, n - 1, 0, n - 1);
  49.     bfs(root);
  50.     return 0;
  51. }