二叉树的后序遍历

ID: 19409

传统题

1000ms

128MiB

尝试: 1

已通过: 1

难度: 10

上传者:

tobyforever

你好，同学。欢迎来到二叉树遍历系列教程的“最终章”——二叉树的后序遍历。

在 NOI 竞赛中，后序遍历（Postorder Traversal）是三者中最具挑战性的，也是用途极广的。它是**树形动态规划（Tree DP）**的核心基础：在处理当前节点（根）之前，必须先收集并处理完左右子树的信息。

一、题目描述 (NOI 风格)

【题目名称】 二叉树的后序遍历 (Binary Tree Postorder Traversal) 【时间限制】 1.0s 【内存限制】 256MB

【问题描述】 给定一棵包含 $n$ 个节点的二叉树，请输出该二叉树的后序遍历序列。后序遍历的顺序为：左子树 -> 右子树 -> 根节点。

由于后序遍历在迭代实现时逻辑最为复杂，本题要求你不仅掌握基础递归，还需深入理解显式栈的维护逻辑，以及 Morris 遍历在后序场景下的特殊变形。

【输入格式】 第一行包含一个整数 $n$ ，表示节点总数。接下来 $n$ 行，每行包含三个整数 $v, l, r$ ，分别表示编号为 $i$ ( $1 \le i \le n$ ) 的节点的权值、左孩子编号和右孩子编号。若无子节点则用 $-1$ 表示。（注：根节点默认为编号 1 的节点。）

【输出格式】 输出一行，包含 $n$ 个整数，表示后序遍历的结果，节点值之间用空格隔开。

【样例 1 输入】

【样例 1 输出】

3 2 1

【数据范围】

树中节点数目 $n$ 范围是 $[0, 100]$ 。
$-100 \le Node.val \le 100$ 。
进阶要求：掌握递归、迭代（显式栈）及 Morris 遍历。

二、预备知识点

后序遍历定义：访问顺序为左右子树全部处理完后，再处理当前根。
状态回溯：在迭代中，需要区分“是从左子树回来”还是“是从右子树回来”。
Morris 逆序处理：Morris 后序遍历需要对左子树的最右侧路径进行临时逆转输出，这是空间 $O(1)$ 的巅峰技巧。

三 : 启发式教学：草稿纸上的推理过程

后序遍历最难的地方在于：你两次路过根节点，但只有第二次路过时才能访问它。

1. 递归思维 (自底向上)

想象你在处理一个公司的财务报表：

你必须先收齐左部门的报告，
再收齐右部门的报告，
最后你才能汇总成总公司的报告（根节点处理）。

2. 迭代思维 (状态记录模型)

在迭代时，我们要用一个 prev 指针记录“上一个访问的节点”。

推演逻辑：
1. 一路向左压栈，直到 curr 为空。
2. 看栈顶节点 $T$ 。
3. 如果 $T$ 有右孩子，且我们不是刚从右孩子回来（即 T->right != prev），那么我们就不能访问 $T$ ，得先去处理右孩子。
4. 否则，说明左右都处理完了，弹出 $T$ 并访问，更新 prev = T。

3. Morris 遍历 (镜像与反转)

Morris 后序遍历非常奇特：

当我们通过线索回到根节点时，说明左子树已经走完。
此时，我们逆序输出左子树最右侧路径上的所有节点。
最后，别忘了在循环结束后单独处理整棵树的最右侧路径。

四、算法流程图 (伪代码逻辑)

1. 递归法逻辑

graph TD
    A("递归开始 Postorder(u)") --> B{"u 为 -1?"}
    B -- "是" --> C["直接返回"]
    B -- "否" --> D["1. 递归左子树 Postorder(tree(u).l)"]
    D --> E["2. 递归右子树 Postorder(tree(u).r)"]
    E --> F["3. 访问并输出 tree(u).val"]
    F --> G["返回"]

2. 迭代法 (显式栈+上一次访问标记) 逻辑

graph TD
    S1("开始") --> S2["curr=root, prev=NULL, 准备栈 S"]
    S2 --> S3{"curr != -1 OR !S.empty?"}
    S3 -- "否" --> SEnd("结束")
    S3 -- "是" --> S4{"curr != -1?"}
    S4 -- "是 (向左钻)" --> S5["压栈 curr, curr=tree(curr).l"]
    S5 --> S4
    S4 -- "否 (触底回溯)" --> S6["取出栈顶 t (不弹出)"]
    S6 --> S7{"tree(t).r != -1 AND tree(t).r != prev?"}
    S7 -- "有右边且未处理" --> S8["curr = tree(t).r"]
    S8 --> S3
    S7 -- "右边已处理或无右边" --> S9["访问 t, prev=t, 弹出栈顶, curr=-1"]
    S9 --> S3

五、复杂度分析与优化建议

时间复杂度： $O(n)$ 。每个节点在递归/迭代中被访问次数恒定。
空间复杂度：
- 递归/迭代： $O(h)$ 。NOI 考场上如果树退化为链且 $n > 10^5$ ，递归会爆栈。
- Morris： $O(1)$ 。后序的 Morris 需要额外的“逆序打印”逻辑，稍微复杂但依然保持 $O(1)$ 空间。

优化建议：

快速输出：后序遍历序列通常很长，NOI 中建议使用 printf 或快读快写。
栈空间：如果不得不使用递归处理深树，可以使用 #pragma comment(linker, "/STACK:...")（取决于竞赛环境允许）或改写迭代。

六、标准题解代码 (NOIP C++14 标准)

版本一：递归法

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 105;
struct Node { int val, l, r; } tree[MAXN];

void postorder(int u) {
    if (u == -1) return;
    postorder(tree[u].l);
    postorder(tree[u].r);
    cout << tree[u].val << " ";
}

int main() {
    int n; cin >> n;
    if (n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> tree[i].val >> tree[i].l >> tree[i].r;
    postorder(1);
    return 0;
}

版本二：迭代法 (推荐，规避爆栈风险)

#include <iostream>
#include <stack>
using namespace std;

const int MAXN = 105;
struct Node { int val, l, r; } tree[MAXN];

void iterativePostorder(int root) {
    if (root == -1) return;
    stack<int> s;
    int curr = root, prev = -1;
    while (curr != -1 || !s.empty()) {
        while (curr != -1) {
            s.push(curr);
            curr = tree[curr].l;
        }
        curr = s.top();
        // 关键点：如果右子树为空，或者右子树刚刚被访问过
        if (tree[curr].r == -1 || tree[curr].r == prev) {
            cout << tree[curr].val << " ";
            prev = curr;
            s.pop();
            curr = -1; // 强制下一轮从栈中取节点
        } else {
            curr = tree[curr].r; // 转向右子树
        }
    }
}

int main() {
    int n; cin >> n;
    if (n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> tree[i].val >> tree[i].l >> tree[i].r;
    iterativePostorder(1);
    return 0;
}

版本三：Morris 遍历 (空间 $O(1)$ 进阶版)

注：逻辑较为繁琐，包含逆转链表操作。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 105;
struct Node { int val, l, r; } tree[MAXN];

// 辅助函数：逆序打印左子树最右路径
void printReverse(int from, int to) {
    vector<int> temp;
    int curr = from;
    while (curr != to) {
        temp.push_back(tree[curr].val);
        curr = tree[curr].r;
    }
    temp.push_back(tree[to].val);
    reverse(temp.begin(), temp.end());
    for (int v : temp) cout << v << " ";
}

void morrisPostorder(int root) {
    if (root == -1) return;
    int dummy = 0; // 建立虚拟节点
    tree[dummy].l = root;
    int curr = dummy;
    while (curr != -1) {
        if (tree[curr].l == -1) {
            curr = tree[curr].r;
        } else {
            int pre = tree[curr].l;
            while (tree[pre].r != -1 && tree[pre].r != curr) pre = tree[pre].r;
            if (tree[pre].r == -1) {
                tree[pre].r = curr;
                curr = tree[curr].l;
            } else {
                tree[pre].r = -1;
                printReverse(tree[curr].l, pre); // 关键：逆序打印
                curr = tree[curr].r;
            }
        }
    }
}

int main() {
    int n; cin >> n;
    if (n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> tree[i].val >> tree[i].l >> tree[i].r;
    morrisPostorder(1);
    return 0;
}

七、读题关键词总结

“后序/末序”：暗示必须先处理完子问题。典型应用：计算子树大小、计算树的高度、销毁树的内存。
“自底向上 (Bottom-up)”：后序遍历的本质思维。
“镜像遍历”：有时可以通过“根-右-左”的顺序遍历后再反转结果，这比标准的后序迭代法更容易实现。

八、数据生成器 (gen_post.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

struct Node { int val, l, r; };

// 迭代法生成标准答案
vector<int> getPost(int n, const vector<Node>& tree) {
    if (n <= 0) return {};
    vector<int> res;
    stack<int> s;
    int curr = 1, prev = -1;
    while (curr != -1 || !s.empty()) {
        while (curr != -1) { s.push(curr); curr = tree[curr].l; }
        curr = s.top();
        if (tree[curr].r == -1 || tree[curr].r == prev) {
            res.push_back(tree[curr].val);
            prev = curr; s.pop(); curr = -1;
        } else curr = tree[curr].r;
    }
    return res;
}

int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int t = 1; t <= 10; ++t) {
        int n = (t <= 2 ? t - 1 : (t * 10)); // 0, 1, 30...100
        vector<Node> tree(n + 1, {0, -1, -1});
        for (int i = 1; i <= n; ++i) tree[i].val = (int)(rng() % 201 - 100);
        
        // 构造随机树
        for (int i = 2; i <= n; ++i) {
            int p = rng() % (i - 1) + 1;
            if (tree[p].l == -1) tree[p].l = i;
            else if (tree[p].r == -1) tree[p].r = i;
        }

        string in_f = to_string(t) + ".in", out_f = to_string(t) + ".out";
        ofstream fin(in_f), fout(out_f);
        fin << n << endl;
        for (int i = 1; i <= n; ++i) fin << tree[i].val << " " << tree[i].l << " " << tree[i].r << endl;
        vector<int> ans = getPost(n, tree);
        for (int i = 0; i < ans.size(); ++i) fout << ans[i] << (i == ans.size() - 1 ? "" : " ");
        fout << endl;
    }
    return 0;
}

教练寄语：后序遍历是通往树上高级算法（如 LCA 离线算法 Tarjan）的必经之路。理解 prev 指针在迭代中的作用，能让你对程序的执行状态有更深刻的把控。加油！

#LC145. 二叉树的后序遍历

一、题目描述 (NOI 风格)

二、预备知识点

三 : 启发式教学：草稿纸上的推理过程

1. 递归思维 (自底向上)

2. 迭代思维 (状态记录模型)

3. Morris 遍历 (镜像与反转)

四、算法流程图 (伪代码逻辑)

1. 递归法逻辑

2. 迭代法 (显式栈+上一次访问标记) 逻辑

五、复杂度分析与优化建议

六、标准题解代码 (NOIP C++14 标准)

版本一：递归法

版本二：迭代法 (推荐，规避爆栈风险)

版本三：Morris 遍历 (空间 $O(1)$ 进阶版)

七、读题关键词总结

八、数据生成器 (gen_post.cpp)

状态

开发

支持

关于

#LC145. 二叉树的后序遍历

二叉树的后序遍历

一、 题目描述 (NOI 风格)

二、 预备知识点

三 : 启发式教学：草稿纸上的推理过程

1. 递归思维 (自底向上)

2. 迭代思维 (状态记录模型)

3. Morris 遍历 (镜像与反转)

四、 算法流程图 (伪代码逻辑)

1. 递归法逻辑

2. 迭代法 (显式栈+上一次访问标记) 逻辑

五、 复杂度分析与优化建议

六、 标准题解代码 (NOIP C++14 标准)

版本一：递归法

版本二：迭代法 (推荐，规避爆栈风险)

版本三：Morris 遍历 (空间 O(1)O(1)O(1) 进阶版)

七、 读题关键词总结

八、 数据生成器 (gen_post.cpp)

状态

开发

支持

关于

还没有账户？

登录

一、题目描述 (NOI 风格)

二、预备知识点

四、算法流程图 (伪代码逻辑)

五、复杂度分析与优化建议

六、标准题解代码 (NOIP C++14 标准)

版本三：Morris 遍历 (空间 $O(1)$ 进阶版)

七、读题关键词总结

八、数据生成器 (gen_post.cpp)