递归dfs易栈溢出且不适用于嵌入式等环境，迭代版用显式栈可控内存并支持中断调试；关键在于栈中存储内容：前序只需节点指针并按右→左压栈，中序需“左到底→弹访→转右”逻辑，后序推荐状态标记法（0/1/2）确保左右子树访问完毕再处理根。
为什么递归DFS不够用，必须写迭代版？
递归DFS在树深度较大时容易触发栈溢出，比如处理上万层的退化链表状二叉树；生产环境也常禁用递归（如嵌入式、实时系统）。迭代版用显式栈控制，内存可控，还能方便加中断逻辑或调试断点。
关键不是“能不能写”，而是“栈里该存什么”。很多人直接塞 TreeNode* 进栈，结果没法区分左右子树访问顺序——这会导致中序/后序遍历错乱。
- 前序遍历：栈中只存节点指针，每次弹出即访问，再按「右→左」顺序压栈（保证左先出）
- 中序/后序：必须带状态标记，例如用
std::pair<treenode int></treenode>，int表示已访问子节点数（0=未访问，1=左已访，2=左右都访完） - 统一写法更可靠：栈存
std::tuple<treenode bool></treenode>，bool标记是否为“回溯节点”（即已访问完子树，只待处理自身）
前序遍历迭代实现怎么写最简？
前序最简单，不需要回溯标记。核心是「访问当前，再把右、左依次压栈」——因为栈是后进先出，这样左子树会先被弹出。
void preorderIterative(TreeNode* root) {
if (!root) return;
std::stack<treenode> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top(); stk.pop();
visit(node); // 你的处理逻辑
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
}</treenode>
注意：压栈顺序不能颠倒。如果先压左再压右，就会变成根→右→左，不是标准前序。
-
visit()是你自己的处理函数，别漏掉 - 空指针检查必须做，否则
node->left可能崩溃 - 用
std::stack而非vector模拟栈，语义清晰且性能不差
中序遍历迭代版最容易错在哪？
错误集中在「什么时候访问节点」。常见写法是走到最左再弹栈访问，但很多人忘了在弹栈后转向右子树——导致右子树被跳过。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
正确逻辑：一路压左到底 → 弹一个访问 → 转向其右子树 → 继续压左到底。
void inorderIterative(TreeNode* root) {
std::stack<treenode> stk;
TreeNode* curr = root;
while (curr || !stk.empty()) {
while (curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top(); stk.pop();
visit(curr);
curr = curr->right;
}
}</treenode>
- 循环条件是
curr || !stk.empty()，缺一不可。仅判栈空会漏掉最右分支 - 内层
while压栈后，curr变成nullptr，靠外层循环的curr = curr->right恢复现场 - 别在压栈时就
visit()——那是前序，不是中序
后序遍历迭代版要不要用两个栈？
单栈能做，但双栈更直观：第一栈模拟递归调用，第二栈存访问顺序。不过实际项目里，用状态标记的单栈更省内存且易调试。
推荐状态标记法：栈存 std::pair<treenode int></treenode>，int 表示「已处理子节点数量」。
void postorderIterative(TreeNode* root) {
if (!root) return;
std::stack<:pair int>> stk;
stk.push({root, 0});
while (!stk.empty()) {
auto [node, state] = stk.top(); stk.pop();
if (state == 0) {
stk.push({node, 1});
if (node->left) stk.push({node->left, 0});
} else if (state == 1) {
stk.push({node, 2});
if (node->right) stk.push({node->right, 0});
} else {
visit(node);
}
}
}</:pair>
状态 0→1→2 对应「未访问子树→左已访→左右都访完」，只有 state==2 才真正访问节点。这个模式可直接迁移到 N 叉树。
真正麻烦的是边界情况：空树、单节点、只有左或右子树——建议用这几个 case 单步调试栈变化过程，比读代码快得多。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
