• 中文 • Walking in Code

深度优先搜索(DFS) - 递归与迭代完全指南

通过交互式可视化掌握DFS算法。学习递归和迭代实现，解决对称二叉树、路径总和等经典问题。完整的Java、Python、JavaScript模板助你征服面试。

#algorithm #dfs #depth-first-search #binary-tree #recursion #stack #visualization #interview

深度优先搜索(DFS)是什么？

深度优先搜索 (Depth-First Search, DFS) 是一种图遍历算法，它沿着树的深度遍历节点，尽可能深地搜索树的分支。当节点的所有子节点都被探索后，再回溯到上一个节点。

为什么面试官喜欢考 DFS？

  1. 考察递归思维：DFS 天然适合用递归实现，考察对递归的理解
  2. 应用广泛：二叉树、图、回溯、动态规划等多个领域都用到 DFS
  3. 变体丰富：可以延伸出大量题目（路径问题、岛屿问题、子集问题等）
  4. 优化空间大：可以考察递归转迭代、剪枝优化等技巧

DFS vs BFS 对比

特性DFS（深度优先）BFS（广度优先）
遍历顺序先深入到底，再回溯逐层遍历
数据结构栈（Stack）或递归队列（Queue）
空间复杂度O(h) - 树高O(w) - 最宽层
适用场景路径查找、拓扑排序、检测环最短路径、层序遍历
实现难度递归简单，迭代稍难迭代实现简单

核心思想：深度优先的遍历策略

DFS 的核心思想可以用一句话概括：

先走到头，走不通再回头

DFS 遍历顺序示例：
        1
       / \
      2   3
     / \   \
    4   5   6

递归 DFS 访问顺序：1 -> 2 -> 4 (回溯) -> 5 (回溯) -> 3 -> 6

DFS 的三个关键步骤

  1. 访问当前节点：处理当前节点的逻辑
  2. 递归子节点：对所有子节点进行 DFS
  3. 回溯：子节点处理完后，返回到父节点

交互式 DFS 可视化

下面的可视化工具展示了 DFS 在不同问题中的应用。你可以选择不同的问题和实现方法，逐步观察 DFS 的执行过程。

Step 1 of 0
1234243
Legend:
Unvisited
Current/Visiting
Comparing
Visited
Found/Match

使用说明：

  • 选择不同的问题类型：对称二叉树、路径总和、最大深度
  • 选择实现方法：递归或迭代
  • 使用播放按钮观察完整的 DFS 过程
  • 使用上一步/下一步按钮仔细观察每一步
  • 查看调用栈/队列状态理解算法执行

DFS 通用模板

掌握 DFS 的关键是记住这个万能模板，90% 的 DFS 题目都可以套用。

Loading...

模板要点：

  1. 递归三要素：

    • 终止条件（何时停止）
    • 处理逻辑（做什么）
    • 递归调用（如何深入）

  2. 迭代关键：

    • 用栈模拟递归
    • 注意入栈顺序（右子树先入，左子树后入）

  3. 回溯时机：

    • 需要恢复状态时使用
    • 典型场景：组合、排列、子集问题

经典问题一：对称二叉树

对称二叉树 (LC 101)

问题描述

给定一个二叉树，检查它是否是镜像对称的。

示例：

    1
   / \
  2   2
 / \ / \
3  4 4  3  ✓ 对称

    1
   / \
  2   2
   \   \
   3    3  ✗ 不对称

解题思路

核心洞察：一棵树对称 ⟺ 左右子树互为镜像

两棵树互为镜像的条件：

  1. 根节点值相同
  2. 树 A 的左子树和树 B 的右子树互为镜像（外侧）
  3. 树 A 的右子树和树 B 的左子树互为镜像（内侧）
镜像对比示意：
    Left        Right
     2            2
    / \          / \
   3   4        4   3
   ↓   ↓        ↓   ↓
   对比外侧：3 vs 3 ✓
   对比内侧：4 vs 4 ✓

解法一：递归（推荐）

Loading...

复杂度分析：

  • 时间复杂度：O(n)O(n)，需要遍历所有节点
  • 空间复杂度：O(h)O(h)，递归栈深度为树高，最坏 O(n)O(n)

解法二：迭代（队列）

Loading...

复杂度分析：

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)，队列最多存储一层节点

关键要点

✅ 正确的对比顺序（镜像）：

isMirror(left.left, right.right)   // 外侧
isMirror(left.right, right.left)   // 内侧

❌ 错误的对比顺序（相同）：

isMirror(left.left, right.left)    // 这是判断相同，不是镜像！
isMirror(left.right, right.right)

经典问题二：路径总和

路径总和 (LC 112)

问题描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，使得路径上所有节点值相加等于目标和。

示例：

        5
       / \
      4   8
     /   / \
    11  13  4
   / \       \
  7   2       1

targetSum = 22
路径: 5 -> 4 -> 11 -> 2 = 22 ✓

解题思路

这是一个典型的 DFS + 回溯 问题：

  1. 递归定义：hasPathSum(node, remaining) 表示从 node 开始，能否找到和为 remaining 的路径
  2. 递推关系：hasPathSum(node, remaining) = hasPathSum(node.left, remaining - node.val) || hasPathSum(node.right, remaining - node.val)
  3. 终止条件：叶子节点时，检查 remaining == node.val
Loading...

复杂度分析：

  • 时间复杂度：O(n)O(n)，最坏情况遍历所有节点
  • 空间复杂度：O(h)O(h)，递归栈深度

变体问题

  • 路径总和 II (LC 113)：返回所有路径（需要回溯）
  • 路径总和 III (LC 437)：路径不一定从根节点开始（双重递归）

经典问题三：二叉树最大深度

二叉树最大深度 (LC 104)

问题描述

给定一个二叉树，找出其最大深度。深度是从根节点到最远叶子节点的最长路径上的节点数。

示例：

    3
   / \
  9  20
    /  \
   15   7

最大深度 = 3

解题思路

这是 DFS 最经典的自底向上问题：

递归定义：

maxDepth(node)={0if node is null1+max⁡(maxDepth(left),maxDepth(right))otherwise\text{maxDepth}(node) = \begin{cases} 0 & \text{if node is null} \\ 1 + \max(\text{maxDepth}(left), \text{maxDepth}(right)) & \text{otherwise} \end{cases}
Loading...

复杂度分析：

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(h)O(h)

举一反三

这个模板可以解决很多”树的属性”问题：

问题递推公式
最小深度1 + min(left, right) (注意叶子节点)
节点个数1 + count(left) + count(right)
是否平衡abs(left - right) <= 1 && balanced(left) && balanced(right)
直径max(left + right, diameter(left), diameter(right))

更多 DFS 经典问题

1. 岛屿数量 (LC 200)

// DFS + 标记已访问
public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    // 边界检查
    if (i < 0 || i >= grid.length || 
        j < 0 || j >= grid[0].length || 
        grid[i][j] == '0') {
        return;
    }
    
    // 标记为已访问
    grid[i][j] = '0';
    
    // 四个方向 DFS
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

2. 二叉树的所有路径 (LC 257)

// DFS + 回溯
public List<String> binaryTreePaths(TreeNode root) {
    List<String> result = new ArrayList<>();
    if (root == null) return result;
    
    dfs(root, String.valueOf(root.val), result);
    return result;
}

private void dfs(TreeNode node, String path, List<String> result) {
    // 叶子节点：添加路径
    if (node.left == null && node.right == null) {
        result.add(path);
        return;
    }
    
    // 递归左子树
    if (node.left != null) {
        dfs(node.left, path + "->" + node.left.val, result);
    }
    
    // 递归右子树
    if (node.right != null) {
        dfs(node.right, path + "->" + node.right.val, result);
    }
}

3. 验证二叉搜索树 (LC 98)

// DFS + 边界检查
public boolean isValidBST(TreeNode root) {
    return dfs(root, null, null);
}

private boolean dfs(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    
    // 检查当前节点是否在合法范围内
    if ((min != null && node.val <= min) || 
        (max != null && node.val >= max)) {
        return false;
    }
    
    // 左子树：上界是当前节点值
    // 右子树：下界是当前节点值
    return dfs(node.left, min, node.val) && 
           dfs(node.right, node.val, max);
}

面试技巧与注意事项

常见错误

❌ 错误1：忘记终止条件

// 错误：会导致空指针
public int maxDepth(TreeNode root) {
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// 正确
public int maxDepth(TreeNode root) {
    if (root == null) return 0;  // ✓ 终止条件
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

❌ 错误2：迭代时栈操作顺序错误

// 错误：会导致 BFS 顺序
stack.push(node.left);   // 左先入
stack.push(node.right);  // 右后入 -> 右先出（变成 BFS）

// 正确：保持 DFS 顺序
stack.push(node.right);  // 右先入
stack.push(node.left);   // 左后入 -> 左先出（DFS）

❌ 错误3：回溯时忘记恢复状态

// 错误：修改了状态但没恢复
void dfs(TreeNode node, List<Integer> path) {
    path.add(node.val);
    dfs(node.left, path);   // path 被修改了
    dfs(node.right, path);  // 左子树的结果影响右子树
}

// 正确：恢复状态
void dfs(TreeNode node, List<Integer> path) {
    path.add(node.val);
    dfs(node.left, path);
    dfs(node.right, path);
    path.remove(path.size() - 1);  // ✓ 回溯：移除当前节点
}

面试沟通技巧

  1. 明确问题类型：

    • “这是一个需要遍历整棵树的问题，我打算用 DFS…”
    • “我们需要找到一条路径，DFS 比 BFS 更合适…”

  2. 说明时间空间复杂度：

    • “递归的空间复杂度是 O(h)，对于平衡树是 O(log n)”
    • “如果担心栈溢出，我可以改用迭代实现…”

  3. 讨论优化方向：

    • “如果需要优化空间，可以用 Morris 遍历…”
    • “如果有大量查询，可以考虑缓存结果…”

边界情况检查清单

✅ 面试时一定要考虑：

  • 空树（root == null）
  • 单节点树
  • 完全不平衡的树（链状）
  • 目标值为负数（路径和问题）
  • 节点值为负数

何时不用 DFS？

虽然 DFS 强大，但有些场景更适合其他算法：

场景不用 DFS 的原因推荐算法
找最短路径DFS 不保证最短BFS
层序遍历DFS 无法按层访问BFS + 队列
判断二分图需要逐层染色BFS
树的宽度需要按层统计BFS

时间与空间复杂度总结

实现方式时间复杂度空间复杂度备注
递归 DFSO(n)O(n)O(h)O(h)h 为树高，最坏 O(n)O(n)
迭代 DFS（栈）O(n)O(n)O(h)O(h)显式栈，同递归
Morris DFSO(n)O(n)O(1)O(1)修改树结构，需恢复

其中 nn 是节点总数，hh 是树的高度：

  • 平衡树：h=O(log⁡n)h = O(\log n)
  • 最坏情况（链状树）：h=O(n)h = O(n)

总结：DFS 核心要点

必须记住的模板

// 递归 DFS 万能模板
void dfs(TreeNode node) {
    if (node == null) return;       // 1. 终止条件
    
    process(node);                  // 2. 处理当前节点
    
    dfs(node.left);                 // 3. 递归左子树
    dfs(node.right);                // 4. 递归右子树
    
    cleanup(node);                  // 5. 回溯（可选）
}

DFS 的三大应用场景

  1. 树的遍历与属性计算

    • 前序/中序/后序遍历
    • 深度、节点数、路径和

  2. 路径问题

    • 路径总和、所有路径
    • 最长路径、路径存在性

  3. 树的结构判断

    • 对称性、相同树、子树
    • BST 验证、平衡性

面试中的 DFS 解题步骤

  1. 识别问题类型：是否需要遍历整棵树？
  2. 选择递归还是迭代：递归优先（简洁），栈溢出风险用迭代
  3. 写出递归三要素：终止条件、处理逻辑、递归调用
  4. 考虑边界情况：空树、单节点、极端情况
  5. 分析复杂度：时间 O(n)O(n)，空间 O(h)O(h)

最后的建议

  • ✅ 多练习：至少掌握 20+ DFS 经典题
  • ✅ 画图理解：递归调用树、栈的变化
  • ✅ 对比 BFS：理解两者的适用场景
  • ✅ 总结模板：记住通用模板，快速套用

记住：DFS 的本质是”深入探索，遇到死胡同就回溯”。掌握这个思想，就掌握了解决树和图问题的核心武器！

Happy Coding! 🚀

← 返回博客列表