企业官网建设流程全解析

Tree Traversals Again，光看英文名容易误以为是一道"再把树的遍历写一遍"的签到题，实际上它把树的三种遍历、非递归栈模拟、序列重建全部串在了一道题里。题目用一段Push/Pop操作序列代替直接给出的树结构，你得先还原二叉树，再输出后序遍历序列。对准备算法笔试、复习数据结构、或者想把手写非递归遍历彻底吃透的人来说，这都是性价比极高的一道综合题。我第一次做的时候也被绕晕了，等我把Push和Pop到底对应什么想明白之后，发现整个解题框架非常清晰。这篇文章就把我的推导过程、手算演示和完整代码一起写下来。

1. 先读懂题意：输入的根本不是树，而是栈的操作轨迹

1.1 输入输出格式里藏着什么

题目给的第一行是节点总数N，接下来一共2N行操作。每一行要么是Push X，表示把节点X压入栈；要么是单独的Pop，表示弹出栈顶节点。节点编号是从1到N的正整数，且各不相同。

举个最简单的例子。假设N=5，输入片段可能是：

Push 1 Push 2 Push 3 Pop Pop Push 5 Pop Pop Push 4 Pop

这10行操作恰好对应一棵含5个节点的二叉树。题目要你输出这棵树的后序遍历序列，节点间用空格分隔，行末不能有多余空格。

这里最迷惑人的地方在于：没有任何一个步骤直接告诉你树长什么样，也没有一个序列是现成的先序或中序。你只能从栈的压入和弹出顺序里反推。所以第一件事不是急着写代码，而是搞清楚Push和Pop各自记录了什么信息。

1.2 先序、中序、后序分别对应哪个操作

常规理解里，三种遍历的差异其实只有一个核心问题："根节点什么时候被访问"。

• 先序遍历：访问根 → 遍历左子树 → 遍历右子树。根被最早访问。
• 中序遍历：遍历左子树 → 访问根 → 遍历右子树。根在中间被访问。
• 后序遍历：遍历左子树 → 遍历右子树 → 访问根。根被最晚访问。

当我们在写非递归中序遍历时，Push代表节点第一次被遇到并暂存起来，Pop代表左子树全部处理完、回到该节点准备访问它。换句话说：

• 每次入栈的节点，按顺序构成了先序遍历序列。
• 每次出栈的节点，按顺序构成了中序遍历序列。

为什么"入栈顺序"是先序而不是中序？看下面这个操作片段就明白了：

Push 1 Push 2 Push 3 Pop Pop Push 4 Pop

Push 1、Push 2、Push 3是在沿左子树向下探索时发生的，这些节点在被push的那一刻就已经被"看到"了，相当于先序遍历里的"访问根节点"动作提前发生。而Pop出来的节点是3、2、1这样的顺序，左子树处理完才轮到中间节点，正是中序遍历。

所以这道题本质上是：给你先序序列（所有Push的节点）和中序序列（所有Pop的节点），让你重建二叉树，然后输出后序。之前的迷惑感会一下子消失。

2. 核心推导：为什么Push序列等于先序，Pop序列等于中序

2.1 非递归中序遍历的教科书逻辑

要理解上面的等价关系，得先回到非递归中序遍历本身。经典的写法是：

stack<Node*> st; Node* p = root; while (p != nullptr || !st.empty()) { while (p != nullptr) { st.push(p); // 沿左子树一路入栈 p = p->left; } if (!st.empty()) { p = st.top(); st.pop(); // 左子树处理完，出栈访问 cout << p->val << " "; p = p->right; // 转向右子树 } }

这段代码里有两处关键动作：

• 入栈发生在p不为空时：此时我们刚"发现"这个节点，正准备继续深入它的左子树。
• 出栈发生在该节点所有左子树节点都处理完之后：此时回到这个节点，输出它，然后转向右子树。

如果我们把"入栈动作"和"出栈动作"分别记录下来，那么入栈动作发生的时机，和先序遍历中"访问根"的时机完全相同；出栈动作发生的时机，和中序遍历中"访问根"的时机完全相同。

2.2 一个容易混淆的概念：两种"访问"不是同一回事

初学者最容易在这里犯迷糊。先序遍历里的"访问"指的是第一次遇到节点就立刻输出。而中序遍历里的"访问"指的是左子树全部跑完、回到节点时输出。两个动作都叫"访问"，但发生时刻完全不同。

用生活中的例子来类比：先序遍历像"进门就登记姓名"，中序遍历像"参观完左侧所有房间，回到客厅才登记姓名"。同一个名字会被登记在不同时间点，所以两种序列自然不同。

在非递归中序遍历代码中，Push对应"进门"这个动作，Pop对应"回到客厅"这个动作。因此：

• 记录所有Push的节点 → 得到先序序列。
• 记录所有Pop的节点 → 得到中序序列。

2.3 用样例验证一下等价关系

还是用开头那个N=5的操作序列，我把每一次操作对应的实际动作列出来：

最终得到：

• 先序序列：1 2 3 5 4
• 中序序列：3 2 5 1 4

树形结构如下：

1 / \ 2 4 / \ 3 5

后序遍历依次访问左、右、根，输出是：3 5 2 4 1。

这个推导是整个题目的灵魂。代码实现反而是水到渠成的事。

3. 先序+中序重建二叉树：手算一遍再写代码

3.1 重建原理：递归切分序列

已知先序序列和中序序列，要重建二叉树，靠的是这样一个递归逻辑：

• 先序序列的第一个元素一定是整棵树的根。
• 在中序序列里找到根的位置，它左边的所有元素属于根的左子树，右边的所有元素属于根的右子树。
• 左子树（或右子树）的中序序列长度是确定的，据此可以把先序序列中根之后的元素也切成左右两段。
• 对左右子树递归执行同样的操作。

步骤只有三步，但很多人第一次实现时会栽在先序序列的左右切分边界上。原因很简单：先序序列里根后面紧跟着一整段左子树先序，然后是右子树先序，但中间没有分隔符，必须依靠中序序列里算出来的长度去切。

3.2 手工推导示例

用上一节的样例：

先序 pre：1 2 3 5 4
中序 in：3 2 5 1 4

第一步，pre[0]=1是根。在中序里找到1的位置是下标3，所以：

• 中序左子树部分：3 2 5，长度为3。
• 中序右子树部分：4，长度为1。
• 先序序列中根之后的前3个元素是左子树先序：2 3 5。
• 剩下1个元素是右子树先序：4。

对左子树递归：

• pre =2 3 5，in =3 2 5。根是2，在中序里的位置是1。
• 左子树中序部分：3，长度1；先序左子树部分：3。
• 右子树中序部分：5，长度1；先序右子树部分：5。

继续对两个叶子节点处理，树就完整还原了。

手算过一遍之后你会发现，整棵树的形状完全由"根在中序中的位置"决定。位置越靠中间，表示左右子树越均衡；位置靠两端，表示树越倾斜。

3.3 指针版代码实现

先写一份最直白的指针版，逻辑清晰，适合用来对照上面的推导：

#include <bits/stdc++.h> using namespace std; struct Node { int val; Node *left, *right; Node(int x) : val(x), left(nullptr), right(nullptr) {} }; int n; vector<int> pre, in, post; Node* build(int preL, int preR, int inL, int inR) { if (preL > preR) return nullptr; Node* root = new Node(pre[preL]); int k = inL; while (in[k] != pre[preL]) k++; // 在中序中查找根的位置 int leftLen = k - inL; root->left = build(preL + 1, preL + leftLen, inL, k - 1); root->right = build(preL + leftLen + 1, preR, k + 1, inR); return root; } void postOrder(Node* root) { if (root == nullptr) return; postOrder(root->left); postOrder(root->right); post.push_back(root->val); } int main() { cin >> n; stack<int> st; string cmd; for (int i = 0; i < 2 * n; i++) { cin >> cmd; if (cmd == "Push") { int x; cin >> x; st.push(x); pre.push_back(x); } else { in.push_back(st.top()); st.pop(); } } Node* root = build(0, n - 1, 0, n - 1); postOrder(root); for (int i = 0; i < n; i++) { cout << post[i] << (i == n - 1 ? '\n' : ' '); } return 0; }

这段代码里，build函数的四个参数分别表示当前子树在先序序列和中序序列中的下标范围。preL到preR是先序范围，inL到inR是中序范围。每次递归，范围都会缩小，直到为空。

3.4 数组版代码：不用new也能建树

有些人习惯在算法竞赛环境里避免使用new，因为手动管理指针容易在某个边界条件下踩内存问题。更稳妥的写法是用结构体数组模拟节点，左右孩子存的是数组下标：

#include <bits/stdc++.h> using namespace std; struct Node { int left, right; // -1 表示空 } tree[100]; int n; vector<int> pre, in, post; int build(int preL, int preR, int inL, int inR) { if (preL > preR) return -1; int root = pre[preL]; int k = inL; while (in[k] != root) k++; int leftLen = k - inL; tree[root].left = build(preL + 1, preL + leftLen, inL, k - 1); tree[root].right = build(preL + leftLen + 1, preR, k + 1, inR); return root; } void postOrder(int root) { if (root == -1) return; postOrder(tree[root].left); postOrder(tree[root].right); post.push_back(root); } int main() { cin >> n; for (int i = 1; i <= n; i++) tree[i].left = tree[i].right = -1; stack<int> st; string cmd; for (int i = 0; i < 2 * n; i++) { cin >> cmd; if (cmd == "Push") { int x; cin >> x; st.push(x); pre.push_back(x); } else { in.push_back(st.top()); st.pop(); } } int root = build(0, n - 1, 0, n - 1); postOrder(root); for (int i = 0; i < n; i++) { cout << post[i] << (i == n - 1 ? '\n' : ' '); } return 0; }

数组版的好处是结束后不需要手动释放内存，所有节点天然存储在线性空间里，调试起来也更直观。我个人在写竞赛题时更常用这种风格。

4. 代码之外的坑位：格式、边界和两个隐蔽问题

4.1 输出格式的"行末空格"细节

这题最常见的非逻辑性丢分点就是行末空格。后序结果要在一行输出，节点间用一个空格隔开，最后一个节点后不能有空格。如果不处理，很多在线评测系统会报"Presentation Error"格式错误。

我习惯用三目运算符一次性搞定：

cout << post[i] << (i == n - 1 ? '\n' : ' ');

这样写比判断if (i != 0) cout << ' ';更紧凑。核心思想就是：把分隔符放在每个元素后面，最后一个元素后面跟换行，而不是把分隔符放在元素前面。

4.2 递归边界的常见错误

build函数最容易写错的地方是递归参数：

root->right = build(preL + leftLen + 1, preR, k + 1, inR);

这里preL + leftLen是指左子树先序的结束位置，右子树先序要从它加1开始。经常有人错写成preL + leftLen或者preL + leftLen + 2，导致越界。

另一个隐蔽问题是：leftLen是根据中序位置k算出来的，k - inL这一项千万不能拿pre的某个下标去替代，两者没有任何直接关系。我见过有人把leftLen写成k - preL，这种错误在样例恰好相等时可能看不出来，换一组数据就直接崩溃或输出错误序列。

4.3 隐藏的假设：节点编号是数组下标

题目保证节点编号从1到N且互不相同，所以数组版代码里可以用tree[root]来存左右孩子。但如果编号范围很大、或者不连续，就不能直接拿编号当下标，必须用map做离散化。

我习惯先读完整输入，确认节点编号之后再做决定。如果确定是1到N，数组版最省心；如果不确定，那就老老实实用unordered_map<int, int>记录节点对应的数组下标，避免空间浪费。

5. 不建树的终极写法：一边递归一边输出后序

5.1 后序遍历本质上是递归分割的输出顺序

有人可能会问：我们真的需要先建一棵树再遍历吗？其实不需要。后序遍历的顺序是"左子树、右子树、根"，这个顺序恰好和我们在build函数里递归处理左右子树的顺序一致。我们完全可以在递归分割序列的过程中，按照左、右、根的顺序把节点输出，省去显式建树和后续遍历两个步骤。

核心思路是：把build函数里的"创建节点"动作，替换成"最后输出节点"动作。

5.2 递归输出版本

#include <bits/stdc++.h> using namespace std; vector<int> pre, in; int n, cnt; void getPost(int preL, int preR, int inL, int inR) { if (preL > preR) return; int root = pre[preL]; int k = inL; while (in[k] != root) k++; int leftLen = k - inL; getPost(preL + 1, preL + leftLen, inL, k - 1); // 左子树 getPost(preL + leftLen + 1, preR, k + 1, inR); // 右子树 // 根放在最后输出 cout << root << (++cnt == n ? '\n' : ' '); }

这个版本非常清爽。getPost的递归结构本身就在"模拟后序遍历的顺序"，中间不需要额外存储任何节点信息。唯一要注意的是输出格式控制，这里用cnt记录已经输出的节点数量，当输出满N个节点时补换行。

5.3 为什么这种写法在比赛中更吃香

显式建树有两个潜在成本：一是代码量更大，二是递归遍历时还要考虑左右孩子是否存在。可读性上，指针版确实更容易让人理解"树正在被重建"，但比赛追求的是快速、正确、少出错。

不建树的版本把"重建"和"输出"合并成一个过程，逻辑闭环更短。只要理解了leftLen的切分方式，后续根本不需要关心树长什么样，直接递归输出即可。我个人在时间紧张时会直接写这个版本，省掉一半代码。

6. 进阶思考：从这道题延伸出去的几个问题

6.1 为什么先序+后序不能唯一重建树

很多人在做完Tree Traversals Again之后会自然想到：既然先序+中序能重建，中序+后序能重建，那先序+后序能不能重建？答案是通常不能唯一重建。

关键原因在于中序序列唯一区分了左子树和右子树的边界。先序序列只告诉我们"根在最前面"，但根的左右子树怎么划分，先序自己说不清楚；后序只告诉我们"根在最后面"，同样无法划分左右边界。

只有当所有节点都只有一个孩子时，先序+后序才能唯一确定树，因为每个子树只有一种挂法。这种边界条件在考试里经常作为判断选项出现，但实际做Tree Traversals Again不会遇到，因为中序序列已经把划分信息给足了。

6.2 用哈希表优化根节点查找

本题N通常不超过30，线性查找根节点位置的复杂度可以接受。但如果N扩大到10万级别，每次递归都做线性查找，总复杂度会退化到O(N²)。

预处理一个unordered_map<int, int> pos，记录每个中序元素的下标，查找根节点的时间就变成O(1)，整体重建复杂度降为O(N)。

int k = pos[root];

这个方法对任何序列重建题目都有效。我习惯在写重建类题目时直接默认使用哈希表，因为代码改动只有几行，却能让算法在更大数据下依然稳定。

6.3 非递归遍历本身还值得多练一遍

这道题之所以叫"Again"，是因为它假设你已经熟悉非递归中序遍历。很多人背代码背得很熟，却说不清Push和Pop的时机，遇到反向题目就发懵。

我的建议是：把非递归三种遍历的栈版本都自己推导一遍，并且每次Push/Pop都标记一下"这个动作对应什么时机"。当你能把栈操作和遍历顺序一一对应起来时，像Tree Traversals Again这种"由操作还原树"的题目就不再是玄学。

提示：做题时如果遇到"给出一段栈操作序列，求某遍历结果"的变体，核心永远是先确定Push序列和Pop序列分别代表先序和中序，然后套重建模板。不要试图从操作序列直接"脑补"树的结构，那是拿样例试探，反而更容易出错。

我自己每次做这类题，都会先在草稿纸上模拟一遍非递归中序遍历的栈过程，写清Push和Pop对应的节点，再开始写代码。这样虽然多花一两分钟，但能避免一半的边界错误。Tree Traversals Again把树的遍历考得非常漂亮，从栈操作出发反推结构，再用递归重建，最后回到后序输出——一环扣一环。把这套流程吃透，不仅这道题稳了，后面遇到类似的序列重建题也能很快反应过来。