当前位置：首页 > news >正文

算法竞赛：从遍历序列完美重建二叉树（先序/后序 + 中序）

news 2026/6/15 23:19:25

算法竞赛：从遍历序列完美重建二叉树（先序/后序 + 中序）

在数据结构与算法竞赛（如 PTA 天梯赛、PAT、ICPC）中，“给定两个遍历序列，求第三个序列（或层序遍历）”几乎是树形结构中最经典的必考题型。

很多初学者在建树时，经常被复杂的递归边界（L, R 的加减一）绕晕，甚至引发段错误。本文将从核心逻辑出发，带你彻底攻克“先序+中序”与“后序+中序”的建树难题，并提供极致精简的 C++ 竞赛模板。

一、核心原理解析：为什么核心永远是“中序”？

要还原一棵二叉树，我们必须明确三种遍历序列的“职能”：

先序遍历 (Preorder)：[根节点] [左子树的先序] [右子树的先序]。它的唯一作用就是告诉我们谁是当前的根节点（永远在序列最前面）。
后序遍历 (Postorder)：[左子树的后序] [右子树的后序] [根节点]。它的作用和先序一样，也是提供根节点（永远在序列最后面）。
中序遍历 (Inorder)：[左子树的中序] [根节点] [右子树的中序]。这是建树的灵魂！只有拿着先序或后序提供的“根节点”，在中序序列中找到它，才能将数组劈成两半，精确划分出左子树和右子树的长度。

经典面试题：为什么“先序 + 后序”无法还原二叉树？

因为当一个节点只有一个孩子时，先序和后序无法区分这个孩子到底是左孩子还是右孩子（它们在这两种序列中的相对位置是一样的），因此必须依赖中序遍历来做基准划分。

二、竞赛级优化：由\(O(N^2)\)优化为 \(O(N)\)

在传统的课本代码中，每次在中序数组中找根节点，都需要写一个 for 循环去遍历查找。这会导致整个建树的时间复杂度退化为 \(O(N^2)\)。

降维打击优化：在读入中序序列时，直接用一个 std::unordered_map<int, int>（如果节点值较小，直接用数组 pos[N] 更快）把“节点值”和“它在中序序列中的下标”绑定起来。这样每次找根节点只需 \(O(1)\) 的时间，总复杂度骤降至 \(O(N)\)！

三、先序 + 中序建树：核心逻辑

1. 核心边界推导

假设我们在递归函数中，当前要处理的中序区间是 [il, ir]，先序区间是 [pl, pr]。

毫无疑问，当前的根节点是 root_val = pre[pl]。
通过哈希表，我们瞬间查到这个根在中序里的下标是 k = pos[root_val]。
计算左子树长度：len = k - il。
递归切割：
- 左子树的中序区间：[il, k - 1]
- 左子树的先序区间：[pl + 1, pl + len]
- 右子树的中序区间：[k + 1, ir]
- 右子树的先序区间：[pl + len + 1, pr]

2. C++ 静态数组建树模板（拒绝 new 节点）

C++

#include <iostream>
#include <unordered_map>
using namespace std;const int N = 100010;
int pre[N], in[N];
int l[N], r[N]; // 静态数组代替左右指针，l[i] 表示节点 i 的左孩子
unordered_map<int, int> pos;// 返回当前子树的根节点值
int build(int il, int ir, int pl, int pr) {if (il > ir) return 0; // 空树返回 0（假设节点值 > 0）int root = pre[pl];         // 先序的第一个就是根int k = pos[root];          // $O(1)$ 找到根在中序的下标int len = k - il;           // 算出左子树的长度// 递归建立左右子树，并挂在当前 root 下l[root] = build(il, k - 1, pl + 1, pl + len);r[root] = build(k + 1, ir, pl + len + 1, pr);return root;
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> pre[i];for (int i = 0; i < n; i++) {cin >> in[i];pos[in[i]] = i; // 记录中序序列中每个值的下标}int root = build(0, n - 1, 0, n - 1);// 此处 root 即为整棵树的根，后续可以直接跑 BFS 进行层序遍历return 0;
}

四、后序 + 中序建树

后序遍历的区别仅仅在于：根节点在后序区间的最后面。

1. 核心边界推导

假设当前中序区间是 [il, ir]，后序区间是 [pl, pr]。

当前的根节点是 root_val = post[pr]。
在中序找根下标 k = pos[root_val]。
计算左子树长度：len = k - il。
递归切割：
- 左子树的中序区间：[il, k - 1]
- 左子树的后序区间：[pl, pl + len - 1] (注意这里是从 pl 开始数 len 个)
- 右子树的中序区间：[k + 1, ir]
- 右子树的后序区间：[pl + len, pr - 1] (最后一位 pr 是根，要排除)

2. C++ 模板代码

C++

#include <iostream>
#include <unordered_map>
using namespace std;const int N = 100010;
int post[N], in[N];
int l[N], r[N];
unordered_map<int, int> pos;int build(int il, int ir, int pl, int pr) {if (il > ir) return 0;int root = post[pr];        // 后序的最后一个是根int k = pos[root];int len = k - il;           // 左子树长度l[root] = build(il, k - 1, pl, pl + len - 1);r[root] = build(k + 1, ir, pl + len, pr - 1);return root;
}

五、实战拔高：建好树后该干嘛？（层序遍历输出）

在绝大多数的 PTA 题目（例如经典的 L2-006 树的遍历）中，题目通常会给你后序和中序，要求你输出层序遍历（Level-order Traversal）。

有了上面的静态数组 l[N] 和 r[N]，层序遍历也就是一个极其简单的 BFS（广度优先搜索）：

C++

#include <queue>
#include <vector>void bfs(int root) {queue<int> q;vector<int> res;q.push(root);while (!q.empty()) {int t = q.front();q.pop();res.push_back(t);if (l[t] != 0) q.push(l[t]); // 压入左孩子if (r[t] != 0) q.push(r[t]); // 压入右孩子}// 格式化输出for (int i = 0; i < res.size(); i++) {cout << res[i] << (i == res.size() - 1 ? "" : " ");}
}