题目

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

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

输入格式

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

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

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

输出格式

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

数据范围

$1 \le N \le 30$

输入样例：

1
2
3

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

输出样例：

1	4 1 6 3 5 7 2

有思路后可在如下网站中提交（题目有一点不同）：

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

思路

首先先要明确前序遍历、中序遍历、后序遍历和层序遍历的基础。并且了解它们的性质。如果不懂，请看文章：二叉树基础

这里简单说一下性质：

后序遍历：遍历结果为“左-右-根”。所以当前结果序列的最后一个元素必定是子树的根节点。并且结果集一定是：左子树-右子树-根节点。左子树的所有节点都排在前面。
中序遍历：遍历结果为“左-根-右”。所以中序遍历可以根据根节点切分左右子树

这种还原树的思路：

还原树都是中序+前序，或者中序+后序。原理是：在前序和后序中，很容易得到子树的根节点。得到了根节点就可以在中序比哪里结果集中得到左右子树。再分割左右子树，递归操作。

并且有一个重要的特性：不会有重复元素。

代码：

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

const int N = 35;
int in[N], post[N], n; // in, post 记录中序遍历和后续遍历的值
unordered_map<int, int> l, r, pos; // l, r记录左右节点的值, pos记录在中序遍历中的值

int build(int l1, int r1, int l2, int r2) { // l1,r1是in[]的左右界，l2,r2是post[]的左右界
    int root = post[r2];
    int k = pos[root]; // k-1-l1 代表左子树有多少个节点
    if (l1 < k) { // 存在左子树,递归操作左子树
        l[root] = build(l1, k-1, l2, l2 + k-1-l1);
    }
    if (r1 > k) { // 存在右子树，递归操作右子树
        r[root] = build(k+1, r1, l2 + k-l1, r2-1);
    }
    return root;
}
void bfs(int root) { // 层序遍历
    queue<int> q;
    q.push(root);
    bool flag = true;
    while (q.size()) {
        auto t = q.front();
        if (flag) {
            cout << t;
            flag = false;
        }
        else cout << ' ' << t;
        q.pop();
        if(l.count(t)) q.push(l[t]);
        if(r.count(t)) q.push(r[t]);
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> in[i];
        pos[in[i]] = i;
    }
    int root = build(0, n-1, 0, n-1); // 构建原树
    
    bfs(root); // 层序遍历树
    
    return 0;
}

代码解释

这里的输入就不用说了。因为考虑到中序遍历可以划分左右子树。但是它后序遍历的左右子树怎么得到。

我们清楚后序遍历的结果性质：左子树-右子树-根节点

所以我们只要知道左子树有多少个节点，就可以划分出左子树了。刚好中序遍历就可以获取到节点个数。

个数为：pos_root - in_l - 1。即，根节点位置（我们在读入中序遍历时就用哈希表存起来了）减去当前集合到左集合，在减去自己这个节点。

所以划分后：

左子树集合：
- 中序遍历：in_l, pos_root - 1
- 后序遍历：post_l, post_l + pos_root - in_l - 1
右子树集合：
- 中序遍历：k+1, in_r
- 后序遍历：post_l + pos_root _ in_l, post_r - 1