C++如何实现二叉树的深度优先搜索 (迭代与递归模式对比)-C++-PHP中文网

递归实现dfs栈溢出风险在于系统栈深度受限，树退化为链表时易崩溃；须预判深度、禁用大对象传递、优先迭代替代，并严格检查空指针。

c++如何实现二叉树的深度优先搜索 (迭代与递归模式对比)

递归实现 DFS 时栈溢出风险在哪

递归写法简洁，但实际调用深度受限于系统栈大小。当二叉树退化为链表（比如所有节点只有右子节点），height 达到 10⁵ 级别时，多数环境会触发 stack overflow 错误，而非抛出异常——程序直接崩溃，调试器可能只显示 Segmentation fault 或无堆栈信息。

避免方式不是“加 try-catch”，而是预判：若题目明确给出节点数上限 > 10⁴，或说明“可能退化为单链”，优先排除纯递归解法。

递归版本必须保证每次调用只压入常数个栈帧（即不传大对象、不嵌套 lambda 捕获大量变量）
可手动限制递归深度（如计数器 > 10000 时提前返回错误码），但属于补救，非根本解法
std::stack 迭代版把栈空间从系统栈移到堆上，只要内存够，就能撑住百万级节点

迭代 DFS 必须用 stack 而非 stack

存值（stack<treenode></treenode>）会导致每次 push 都触发深拷贝，不仅性能差（节点含指针成员时拷贝无意义），更关键的是：原始树结构被破坏后，左右子节点指针可能悬空或指向临时对象，后续 pop 出来的节点访问 left/right 会得到未定义行为（常见表现为 nullptr 或随机地址，val 字段偶尔还能读对，极具迷惑性）。

正确做法是只存指针，并确保树本身生命周期覆盖整个遍历过程：

永远用 stack<treenode></treenode> 或 stack<treenode const></treenode>
若树由智能指针管理（如 unique_ptr<treenode></treenode>），则用 stack<treenode></treenode> 仍安全——取 ptr.get() 即可
切勿在迭代过程中 delete 当前节点，否则后续 pop 出的节点指针立刻失效

前序/中序/后序迭代写法差异只在「访问时机」和「入栈顺序」

三者共用同一套栈结构，区别仅在于：节点指针何时算“被访问”，以及子节点入栈是否需要标记状态。最简方案是统一用 pair：一个指针 + 一个整数状态（0=未访问子树，1=已处理左，2=已处理右）。但实际工程中，前序可最简，后序最难。

C++

"空空如也"

下载

例如前序迭代：

stack<treenode> stk;
if (root) stk.push(root);
while (!stk.empty()) {
    TreeNode* n = stk.top(); stk.pop();
    visit(n); // ← 访问放最前
    if (n->right) stk.push(n->right); // 右先入，保证左先出
    if (n->left)  stk.push(n->left);
}</treenode>

而中序需“一路向左压栈，再逐层弹出并转向右”；后序若不用状态标记，则需两个栈或额外 set 记录已访问右子树的节点——这些细节一旦写错，visit() 调用顺序就乱了，且很难通过小样例发现（比如满二叉树下三种顺序都看似正常，但斜树立刻暴露）。

递归与迭代在 nullptr 处理上容易漏掉边界检查

很多人写递归 DFS 时习惯这样开头：if (!root) return;，没问题。但一转成迭代，常犯错误是 push 前没判空，导致 stk.push(nullptr)，随后 stk.top()->left 直接崩。同样，迭代中 pop 后也必须立即判空再访问，不能假设栈里全是有效指针。