分别用显式栈模拟前序、中序、后序遍历，其中后序用双栈避免深递归爆栈。
OJ: luogu
题目 ID: B3642
难度:入门
标签:二叉树树形结构递归
日期: 2026-06-19 22:38
题意
给出一棵以 1 为根的二叉树，要求依次输出它的：
- 前序遍历
- 中序遍历
- 后序遍历
思路
最直接的办法是写三个递归函数。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
static vector<int> left_son;
static vector<int> right_son;
static vector<int> preorder;
static vector<int> inorder;
static vector<int> postorder;
void dfs_pre(int u) {
if (u == 0) {
return;
}
preorder.push_back(u);
dfs_pre(left_son[u]);
dfs_pre(right_son[u]);
}
void dfs_in(int u) {
if (u == 0) {
return;
}
dfs_in(left_son[u]);
inorder.push_back(u);
dfs_in(right_son[u]);
}
void dfs_post(int u) {
if (u == 0) {
return;
}
dfs_post(left_son[u]);
dfs_post(right_son[u]);
postorder.push_back(u);
}
void print_sequence(const vector<int> &seq) {
for (int i = 0; i < (int)seq.size(); ++i) {
if (i) {
cout << ' ';
}
cout << seq[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
left_son.assign(n + 1, 0);
right_son.assign(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> left_son[i] >> right_son[i];
}
dfs_pre(1);
dfs_in(1);
dfs_post(1);
print_sequence(preorder);
print_sequence(inorder);
print_sequence(postorder);
return 0;
}brute.cpp 直接按定义递归，写法最短，也最容易理解。
正式解之所以还要改写，是因为 n 可以到 10^6，树如果退化成链，递归深度会非常危险。
样例树
这张图展示样例树的结构：
graph TD A["1"] --> B["2"] A --> C["7"] B --> D["4"] D --> E["3"] C --> F["6"] F --> G["5"]
对着这张图看：
- 前序是根先走，所以得到
1 2 4 3 7 6 5 - 中序是左边走完再记根，所以得到
4 3 2 1 6 5 7 - 后序是左右都走完再记根，所以得到
3 4 2 5 6 7 1
为了避免递归爆栈，正式解把三种遍历都改成显式栈：
- 前序：先压右，再压左
- 中序：模拟“一路向左深入”
- 后序：用双栈先得到“根右左”，再反过来输出成“左右根”
代码
cpp
#include <bits/stdc++.h>
using namespace std;
void print_sequence(const vector<int> &seq) {
for (int i = 0; i < (int)seq.size(); ++i) {
if (i) {
cout << ' ';
}
cout << seq[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> left_son(n + 1), right_son(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> left_son[i] >> right_son[i];
}
vector<int> preorder;
vector<int> inorder;
vector<int> postorder;
preorder.reserve(n);
inorder.reserve(n);
postorder.reserve(n);
// 前序：根 -> 左 -> 右。
vector<int> st;
st.push_back(1);
while (!st.empty()) {
int u = st.back();
st.pop_back();
if (u == 0) {
continue;
}
preorder.push_back(u);
if (right_son[u] != 0) {
st.push_back(right_son[u]);
}
if (left_son[u] != 0) {
st.push_back(left_son[u]);
}
}
// 中序：左 -> 根 -> 右。
st.clear();
int cur = 1;
while (cur != 0 || !st.empty()) {
while (cur != 0) {
st.push_back(cur);
cur = left_son[cur];
}
cur = st.back();
st.pop_back();
inorder.push_back(cur);
cur = right_son[cur];
}
// 后序：左 -> 右 -> 根。用双栈避免深递归。
vector<int> st2;
st.push_back(1);
while (!st.empty()) {
int u = st.back();
st.pop_back();
if (u == 0) {
continue;
}
st2.push_back(u);
if (left_son[u] != 0) {
st.push_back(left_son[u]);
}
if (right_son[u] != 0) {
st.push_back(right_son[u]);
}
}
for (int i = (int)st2.size() - 1; i >= 0; --i) {
postorder.push_back(st2[i]);
}
print_sequence(preorder);
print_sequence(inorder);
print_sequence(postorder);
return 0;
}复杂度
每个节点都只被访问常数次，所以总时间复杂度是
总结
这题本身是基础遍历题，但数据范围提醒我们要注意实现方式。树很深时，递归和显式栈的差别会直接决定程序能不能过。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
