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

从LeetCode 938到200一套DFS模板解决树与图的经典问题在算法竞赛和面试准备中深度优先搜索DFS是解决树形结构和图论问题的利器。许多初学者在面对不同场景时往往会陷入学一道题只会一道题的困境实际上通过抽象出通用的DFS框架可以举一反三解决大量问题。本文将以LeetCode 938二叉搜索树范围和和200岛屿数量为例展示如何用同一套DFS思维模型应对树和图这两类看似迥异的数据结构。1. DFS核心框架解析深度优先搜索的本质是一条路走到底的探索策略。无论是处理二叉树还是网格图其核心都可以抽象为三个关键步骤处理当前节点对当前访问的节点执行业务逻辑如判断值范围、标记访问等递归子问题按照特定顺序访问相邻节点二叉树是左右子节点网格是四/八邻域处理返回值将子问题的结果与当前节点信息整合后返回这个通用模板可以用伪代码表示为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, i1, j) dfs(grid, i-1, j) dfs(grid, i, j1) dfs(grid, i, j-1)2. 两类问题的对比与转换虽然树和图的问题看起来差异很大但从DFS视角可以找到诸多共性特性二叉树 (LeetCode 938)网格图 (LeetCode 200)节点表示TreeNode对象矩阵坐标(i,j)相邻节点访问固定的left/right子节点动态的四/八邻域坐标访问标记不需要天然无环必须修改原矩阵或使用额外空间记录递归终止条件节点为None越界或不符合条件剪枝优化利用BST特性提前终止分支无特殊优化结果聚合累加符合条件的节点值统计连通区域数量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, depth0): print( *depth fVisit {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网格问题同样可以改为栈实现的DFSdef 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((x1,y)) stack.append((x-1,y)) stack.append((x,y1)) stack.append((x,y-1)) return count4. 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(i1,j) dfs(i-1,j) dfs(i,j1) 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_area4.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 时间复杂度分析二叉树DFSO(N)每个节点访问一次网格DFSO(M×N)最坏情况下访问所有单元格对于特定问题可能需要进行更精确的分析。例如在二叉搜索树范围和中利用BST特性可以实现剪枝平均时间复杂度可能优于O(N)。5.2 空间复杂度考量递归调用栈二叉树最坏O(H)H为树高网格最坏O(M×N)如蛇形矩阵标记存储网格问题可能需要额外O(M×N)空间如果不修改原矩阵5.3 常见错误规避忘记终止条件导致无限递归错误的状态回退回溯问题中忘记恢复状态重复计算未使用记忆化技术优化错误的方向处理网格问题中遗漏某些方向在竞赛和面试场景中建议先写出基础DFS解法再根据问题特点进行优化。对于特别大规模的数据可能需要考虑迭代实现或更高级的算法。