本文讲解二叉树后序遍历的 C++ 迭代实现。对比递归与迭代法的优劣，重点分析迭代实现的难点。提供两种核心解法：一是利用前序遍历逆序技巧快速实现；二是使用 prev 指针标记右子树状态的本质解法。包含代码示例、复杂度分析及实际应用场景，帮助理解栈在遍历中的回溯模拟机制。
给定一个二叉树的根节点 root，返回它的 后序遍历。后序遍历的定义为：按照「左子树 → 右子树 → 根节点」的顺序遍历二叉树的所有节点。
提示：树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
示例 1：输入：root = [1,null,2,3] 输出：[3,2,1] 解释：
后序遍历顺序：3（左子树）→ 2（右子树）→ 1（根节点）
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
后序遍历的递归实现极其简单，核心逻辑贴合定义：
#include <vector>
using namespace std;
// 二叉树节点结构体定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
// 三种构造函数（适配不同节点创建场景）
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
// 主函数：对外暴露的接口，返回后序遍历结果
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
private:
// 辅助递归函数：核心后序遍历逻辑（左→右→根）
void postorder(TreeNode* root, vector<int>& res) {
if (!root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
};
#include <iostream>
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
Solution sol;
vector<int> result = sol.postorderTraversal(root);
cout << "后序遍历结果：";
for (int val : result) {
cout << val << " ";
}
cout << endl;
//释放，避免内存泄漏
delete root->right->left;
delete root->right;
delete root;
return 0;
}
递归的优势在于：函数调用栈会自动维护「回溯顺序」，无需手动记录节点状态 —— 访问完左子树后，自然回溯到父节点，再访问右子树，最后处理根节点。
但递归的局限性也很明显：
迭代法需要手动用栈模拟递归的「回溯过程」，但后序遍历的「左→右→根」顺序存在一个关键矛盾：
这也是迭代法实现的关键。如何精准判断「右子树是否已处理」，成为迭代法实现的核心。
由于前序遍历的迭代写法（根→左→右）非常简洁，初学者常照搬逻辑，仅调整压栈顺序：
// 错误代码：本质是「根→右→左」，反转后才是后序
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* curr = st.top();
st.pop();
ans.push_back(curr->val); // 先访问根节点（错误核心）
if (curr->left) st.push(curr->left); // 先压左
if (curr->right) st.push(curr->right); // 后压右
}
return ans;
}
以示例 1 的树（1→2→3）为例，错误代码的执行流程：
核心错误：后序遍历要求「根节点最后访问」，但该写法先访问根节点，导致顺序完全颠倒 —— 本质是「根→右→左」的前序变种，而非后序。
既然错误写法得到的是「根→右→左」，而后序是「左→右→根」，两者恰好是逆序关系！这启发了第一个可行方案：
这个思路的优势是无需判断子树状态，完全复用前序遍历的逻辑，仅需添加反转步骤 —— 适合快速 AC，但不够贴合后序遍历的本质。
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* curr = st.top();
st.pop();
ans.push_back(curr->val); // 按「根→右→左」收集
// 关键：先压左子树，再压右子树（栈后进先出，确保先访问右子树）
if (curr->left != nullptr) {
st.push(curr->left);
}
if (curr->right != nullptr) {
st.push(curr->right);
}
}
reverse(ans.begin(), ans.end()); // 反转得到后序
return ans;
}
};
这是最能体现后序遍历本质的解法，核心是用 prev 指针记录「上一个访问的节点」，通过判断「当前节点的右子树是否已处理」，决定是否访问当前节点。
prev 指针的核心作用：标记「已处理完毕的节点」—— 后序遍历中，只有当右子树为空或右子树的根节点是 prev 时，说明右子树已处理，才能访问当前根节点；prev。class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;
stack<TreeNode*> stk;
TreeNode* prev = nullptr; // 标记上一个访问的节点（已处理完毕）
while (root != nullptr || !stk.empty()) {
// 第一步：一路向左深探，压入所有左子树节点（确保左优先）
while (root != nullptr) {
stk.emplace(root);
root = root->left;
}
// 第二步：弹出栈顶节点（当前子树的根）
root = stk.top();
stk.pop();
// 关键判断：右子树是否已处理（空或已访问）
if (root->right == nullptr || root->right == prev) {
res.emplace_back(root->val); // 访问根节点（左、右均已处理）
prev = root; // 更新 prev 为当前节点（标记为已处理）
root = nullptr; // 置空 root，下一轮直接从栈取节点（回溯）
} else {
// 右子树未处理：重新压栈当前根，转向右子树
stk.emplace(root);
root = root->right; // 处理右子树（右子树也会先深探左子树）
}
}
return res;
}
};
目标结果：[3,2,1]
prev 指针的标记逻辑，代码稍复杂，需多练习掌握。| 解法类型 | 核心思路 | 时间复杂度 | 空间复杂度 | 代码复杂度 | 面试适配度 |
|---|---|---|---|---|---|
| 递归法 | 函数调用栈维护回溯 | O(n) | O(h) | 极低 | 一般（未满足进阶要求） |
| 前序逆序法 | 根→右→左 + 结果反转 | O(n) | O(h) | 低 | 一般（偏技巧） |
| prev 指针标记法 | 栈 + 指针标记右子树状态 | O(n) | O(h) | 中等 | 高（体现本质理解） |
后序遍历的核心特性是「先处理子树，再处理父节点」，在工程实践中有明确应用：
root==nullptr，直接返回空结果，避免空指针错误；prev 指针的更新：只有当节点被访问（加入结果集）后，才能更新 prev，否则会导致状态判断错误。掌握后序遍历的迭代逻辑后，可快速迁移到中序遍历（左→根→右），只需调整「访问根节点」的时机：
本题的核心启示在于：迭代法的本质是「手动模拟递归的回溯过程」，而难点在于「状态记录」—— 当递归的 '天然记忆' 消失时，需要用额外的指针（如 prev）或技巧（如结果反转）来弥补。
刷题的关键不是 '记住代码'，而是 '理解问题的核心矛盾'—— 后序遍历的矛盾是「根节点的访问时机」，解决了这个矛盾，迭代法自然水到渠成。如果暂时没有思路，建议先从递归写法入手，拆解其回溯过程，再尝试用栈手动模拟，逐步培养迭代思维。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online