深度优先搜索（DFS）系统分类与经典题型详解

深度优先搜索（Depth-First Search, DFS） 是算法中解决树/图遍历、路径搜索、排列组合等问题的核心方法之一。其核心思想是“一条路走到底”的搜索策略，通常通过递归或显式栈实现。

本文从基础概念到经典题型进行系统分类与解析，涵盖从入门到进阶的所有常见问题。

---

一、DFS的三大核心要素

1. 递归终止条件：何时结束当前分支的搜索

   示例：越界、找到目标、访问过

2. 当前层处理：对当前节点或状态的修改

   示例：标记已访问、加入路径

3. 向子问题递归：进入下一层搜索

   示例：遍历相邻节点、选择下一个数字

---

二、DFS经典题型分类

1. 树/图的遍历

（1）基础遍历

🌳 94. 二叉树的中序遍历

python
def inorderTraversal(root):
    res = []
    def dfs(node):
        if not node: return
        dfs(node.left)     # 左
        res.append(node.val) # 中
        dfs(node.right)    # 右
    dfs(root)
    return res

📐 133. 克隆图

• 关键点：使用哈希表记录原节点与克隆节点的映射，避免重复克隆

（2）路径搜索

🧭 112. 路径总和

python
def hasPathSum(root, target):
    if not root: return False
    if not root.left and not root.right:  # 叶子节点
        return target == root.val
    return hasPathSum(root.left, target - root.val) or \
           hasPathSum(root.right, target - root.val)

🧩 437. 路径总和 III

• 双重DFS：外层遍历所有节点，内层计算以当前节点为起点的路径和

---

2. 回溯法（组合 / 排列 / 子集）

（1）组合问题

🎁 39. 组合总和

python
def combinationSum(candidates, target):
    res = []
    def dfs(start, path, remain):
        if remain == 0:
            res.append(path.copy())
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain: continue
            path.append(candidates[i])
            dfs(i, path, remain - candidates[i])  # 可重复选
            path.pop()
    dfs(0, [], target)
    return res

（2）排列问题

🔀 46. 全排列

python
def permute(nums):
    res = []
    def dfs(path, used):
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            dfs(path, used)
            path.pop()
            used[i] = False
    dfs([], [False]*len(nums))
    return res

（3）子集问题

📦 78. 子集

python
def subsets(nums):
    res = []
    def dfs(start, path):
        res.append(path.copy())  # 所有节点都是解
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)  # 不可重复选
            path.pop()
    dfs(0, [])
    return res

---

3. 网格类DFS（岛屿问题）

（1）连通区域计数

🏝️ 200. 岛屿数量

python
def numIslands(grid):
    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '0'  # 标记为已访问
        dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)  # 四方向搜索
    
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

（2）回溯型搜索

🧾 79. 单词搜索

python
def exist(board, word):
    def dfs(i, j, k):
        if k == len(word): return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
            return False
        tmp, board[i][j] = board[i][j], '/'  # 临时标记
        res = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
        board[i][j] = tmp  # 恢复
        return res
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(i, j, 0): return True
    return False

---

4. 记忆化DFS（优化重复计算）

📈 329. 矩阵中的最长递增路径

python
def longestIncreasingPath(matrix):
    if not matrix: return 0
    memo = [[0]*len(matrix[0]) for _ in range(len(matrix))]
    def dfs(i, j):
        if memo[i][j] != 0: return memo[i][j]
        max_len = 1
        for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] > matrix[i][j]:
                max_len = max(max_len, dfs(x, y) + 1)
        memo[i][j] = max_len
        return max_len
    
    return max(dfs(i, j) for i in range(len(matrix)) for j in range(len(matrix[0])))

---

三、DFS解题技巧总结

1. ✂️ 剪枝优化：提前终止无效分支（如组合总和中跳过大于剩余值的候选）
2. 🧭 方向数组：网格类问题用 dirs = [(-1,0),(1,0),(0,-1),(0,1)] 简化四方向遍历
3. 🔁 恢复现场：回溯时务必撤销对状态的修改（如 path.pop() 和 board[i][j] = tmp）
4. 🚧 避免重复访问：用 visited 数组或标记法（如 '/' 或 False/True）

---

四、高频DFS题目列表

类型	经典题目
树/图遍历	94. 中序遍历、133. 克隆图
回溯法	39. 组合总和、46. 全排列
网格类DFS	200. 岛屿数量、79. 单词搜索
记忆化DFS	329. 最长递增路径
复杂回溯	51. N皇后、37. 解数独

---

五、总结

DFS 的核心在于通过递归或栈实现深度优先的穷举搜索。

掌握要点：

1. 明确递归的三个要素（终止条件、当前处理、子问题递归）
2. 区分遍历型 DFS 与回溯型 DFS：
   • 遍历型不修改路径（如树遍历）
   • 回溯型需要“撤销选择”
3. 掌握剪枝与记忆化技巧提升效率

---

📌 推荐练习顺序：树/图遍历 → 回溯法 → 网格类问题 → 记忆化DFS → 复杂回溯