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

递归dfs简洁但有栈溢出风险，适用于树高可控场景；迭代dfs用std::stack避免栈溢出，需注意压栈顺序，适合资源受限环境或深度不可控场景。

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

递归实现DFS：简洁但要注意栈溢出风险

递归写法最贴近DFS的逻辑本质——每次访问节点后，立刻深入左子树或右子树。C++中只需几行就能完成前序遍历：

void dfs_recursive(TreeNode* root) {
    if (!root) return;
    visit(root);           // 比如打印值
    dfs_recursive(root->left);
    dfs_recursive(root->right);
}

关键点在于：递归隐式使用调用栈，天然满足“深度优先”顺序；但当树退化为链表（比如只有左子节点）且高度超过系统栈限制（通常几百到几万层），std::stack overflow会直接崩溃。

适用场景：TreeNode结构稳定、树高可控（如平衡二叉树、红黑树节点遍历）
参数差异：递归函数必须传入当前root指针，不能省略空指针检查
容易踩的坑：忘记if (!root) return;导致空指针解引用，错误信息通常是segmentation fault或Access violation

迭代实现DFS：用`std::stack`模拟调用栈

迭代版把递归的隐式栈显式化，避免栈溢出，也更容易控制遍历顺序（比如想先右后左，只需调整入栈顺序）。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

void dfs_iterative(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>

注意：这里压栈顺序和递归顺序相反——因为栈是LIFO，要让左子树先被处理，就得先压右子树。

常见错误现象：左右子节点压栈顺序颠倒，导致遍历变成“右根左”，和预期不符
性能影响：std::stack默认基于std::deque，内存分配比递归稍多，但时间复杂度仍是O(n)
兼容性：C++11及以上均可，无需额外依赖；若用std::vector做底层容器（std::stack<treenode std::vector>></treenode>），可减少内存碎片

如何选择递归还是迭代？看树结构和运行环境

不是“哪个更好”，而是“哪个更稳”。实际项目里往往得看部署环境：

嵌入式或资源受限设备（如单片机）：强制用迭代，避免不可控的栈空间消耗
LeetCode或算法题：递归更短、不易错，但提交前务必确认maxDepth是否可能超1000
生产服务中处理用户上传的JSON生成的树：必须用迭代，并加深度限制（比如if (depth > 1000) throw std::runtime_error("tree too deep");）
调试时想打断点观察每层状态：递归更容易单步，迭代需关注stk.top()和stk.size()

还有一点常被忽略：递归版本修改为中序/后序遍历只需调整visit()位置；而迭代版本中序需要额外记录“是否已访问过左子树”的状态，后序则需双栈或标记法——复杂度跃升。