从LeetCode 938（二叉搜索树范围和）到200（岛屿数量）：一套DFS模板刷通两类高频题

从LeetCode 938到200：一套DFS模板解决树与图的经典问题

在算法竞赛和面试准备中，深度优先搜索（DFS）是解决树形结构和图论问题的利器。许多初学者在面对不同场景时往往会陷入"学一道题只会一道题"的困境，实际上，通过抽象出通用的DFS框架，可以举一反三解决大量问题。本文将以LeetCode 938（二叉搜索树范围和）和200（岛屿数量）为例，展示如何用同一套DFS思维模型应对树和图这两类看似迥异的数据结构。

1. DFS核心框架解析

深度优先搜索的本质是"一条路走到底"的探索策略。无论是处理二叉树还是网格图，其核心都可以抽象为三个关键步骤：

1. 处理当前节点：对当前访问的节点执行业务逻辑（如判断值范围、标记访问等）
2. 递归子问题：按照特定顺序访问相邻节点（二叉树是左右子节点，网格是四/八邻域）
3. 处理返回值：将子问题的结果与当前节点信息整合后返回

这个通用模板可以用伪代码表示为：

def dfs(node, ...): # 终止条件判断 if not node: return base_case # 处理当前节点（前序位置） process_current_node(node) # 递归子问题 left_result = dfs(node.left, ...) right_result = dfs(node.right, ...) # 整合结果（后序位置） return combine_results(node, left_result, right_result)

1.1 二叉树场景的DFS特点

在二叉树问题中，DFS通常表现出以下特征：

• 访问顺序灵活：前序、中序、后序遍历对应不同处理时机
• 递归方向明确：只需处理左右两个子节点
• 天然无环：不需要额外记录访问状态

以LeetCode 938为例，二叉搜索树的特性允许我们在递归过程中进行剪枝：

def rangeSumBST(root, low, high): if not root: return 0 if root.val > high: # 只需搜索左子树 return rangeSumBST(root.left, low, high) if root.val < low: # 只需搜索右子树 return rangeSumBST(root.right, low, high) # 当前节点在范围内，累加三部分 return (root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high))

1.2 网格图场景的DFS特点

网格图（二维矩阵）中的DFS则有所不同：

• 四/八方向扩展：需要处理多个相邻单元格
• 必须记录访问状态：防止重复访问形成死循环
• 边界检查必要：确保不会越界访问

LeetCode 200的岛屿计数问题展示了这些特点：

def numIslands(grid): if not grid: return 0 count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': count += 1 dfs(grid, i, j) return count def dfs(grid, i, j): # 边界条件和终止条件 if (i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1'): return grid[i][j] = '0' # 标记为已访问 # 四方向递归 dfs(grid, i+1, j) dfs(grid, i-1, j) dfs(grid, i, j+1) dfs(grid, i, j-1)

2. 两类问题的对比与转换

虽然树和图的问题看起来差异很大，但从DFS视角可以找到诸多共性：

2.1 访问标记的差异处理

在树结构中，由于父子关系的单向性，我们不需要担心重复访问问题。但在网格图中，必须对已访问的节点进行标记，否则会陷入无限循环。例如在岛屿问题中，将访问过的'1'改为'0'就是典型的"就地标记"技巧。

2.2 递归方向的动态调整

二叉树的递归方向是固定的（先左后右），而网格图的递归方向可以根据问题需求灵活调整。某些问题可能只需要检查两个方向（如向右和向下），而大多数连通性问题需要检查四个基本方向。

方向数组是处理网格类问题的实用技巧：

# 四方向 directions = [(-1,0), (1,0), (0,-1), (0,1)] # 八方向 directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] def dfs(grid, i, j): grid[i][j] = '0' for di, dj in directions: ni, nj = i + di, j + dj if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]): if grid[ni][nj] == '1': dfs(grid, ni, nj)

3. 调试DFS算法的实用技巧

DFS算法常见的调试难点包括递归深度过大、条件判断不全、状态标记错误等。以下是一些实用技巧：

3.1 可视化递归过程

在二叉树问题中，可以打印缩进来显示递归层级：

def rangeSumBST(root, low, high, depth=0): print(' '*depth + f'Visit {root.val if root else None}') if not root: return 0 # 其余逻辑不变...

对于网格问题，可以在每次递归前后打印矩阵状态：

def dfs(grid, i, j): print(f'\nBefore visit ({i},{j}):') for row in grid: print(row) # 处理逻辑... print(f'\nAfter visit ({i},{j}):') for row in grid: print(row)

3.2 边界条件检查清单

编写DFS时，建议系统性地检查以下边界条件：

• 树问题：

  • 空节点处理
  • 单节点树
  • 完全倾斜的树（如只有左子树）

• 网格问题：

  • 空矩阵或1x1矩阵
  • 全'0'或全'1'的情况
  • 边界上的单元格访问

3.3 递归深度限制问题

Python默认递归深度限制约为1000层，对于大规模问题可能需要改为迭代实现。二叉树问题中，迭代DFS可以使用显式栈：

def rangeSumBST_iter(root, low, high): stack = [] total = 0 while root or stack: while root: stack.append(root) root = root.left root = stack.pop() if low <= root.val <= high: total += root.val root = root.right return total

网格问题同样可以改为栈实现的DFS：

def numIslands_iter(grid): if not grid: return 0 stack = [] count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': count += 1 stack.append((i,j)) while stack: x, y = stack.pop() if (0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1'): grid[x][y] = '0' stack.append((x+1,y)) stack.append((x-1,y)) stack.append((x,y+1)) stack.append((x,y-1)) return count

4. DFS模板的扩展应用

掌握基础DFS框架后，可以解决更多变种问题。以下是几个典型例子：

4.1 二叉树路径问题

LeetCode 112（路径总和）要求判断是否存在从根到叶子的路径和等于目标值：

def hasPathSum(root, target): if not root: return False if not root.left and not root.right: return root.val == target return (hasPathSum(root.left, target - root.val) or hasPathSum(root.right, target - root.val))

4.2 网格的复杂变种

LeetCode 695（岛屿最大面积）在基础岛屿问题上增加了面积计算：

def maxAreaOfIsland(grid): max_area = 0 def dfs(i, j): if (i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != 1): return 0 grid[i][j] = 0 return (1 + dfs(i+1,j) + dfs(i-1,j) + dfs(i,j+1) + dfs(i,j-1)) for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 1: max_area = max(max_area, dfs(i,j)) return max_area

4.3 记忆化搜索优化

对于存在重复子问题的情况（如LeetCode 337打家劫舍III），可以结合记忆化技术：

def rob(root): memo = {} def dfs(node): if not node: return 0 if node in memo: return memo[node] # 抢当前节点 rob_it = node.val if node.left: rob_it += dfs(node.left.left) + dfs(node.left.right) if node.right: rob_it += dfs(node.right.left) + dfs(node.right.right) # 不抢当前节点 not_rob = dfs(node.left) + dfs(node.right) memo[node] = max(rob_it, not_rob) return memo[node] return dfs(root)

5. 性能优化与注意事项

虽然DFS模板通用性强，但在实际应用中仍需注意以下性能问题：

5.1 时间复杂度分析

• 二叉树DFS：O(N)，每个节点访问一次
• 网格DFS：O(M×N)，最坏情况下访问所有单元格

对于特定问题，可能需要进行更精确的分析。例如在二叉搜索树范围和中，利用BST特性可以实现剪枝，平均时间复杂度可能优于O(N)。

5.2 空间复杂度考量

• 递归调用栈：二叉树最坏O(H)（H为树高），网格最坏O(M×N)（如蛇形矩阵）
• 标记存储：网格问题可能需要额外O(M×N)空间（如果不修改原矩阵）

5.3 常见错误规避

1. 忘记终止条件：导致无限递归
2. 错误的状态回退：回溯问题中忘记恢复状态
3. 重复计算：未使用记忆化技术优化
4. 错误的方向处理：网格问题中遗漏某些方向

在竞赛和面试场景中，建议先写出基础DFS解法，再根据问题特点进行优化。对于特别大规模的数据，可能需要考虑迭代实现或更高级的算法。