LeetCode 双杀！二叉树最大路径和 + 岛屿数量｜DFS 两大经典模板题

前言DFS深度优先搜索是算法面试的核心技能它不仅适用于二叉树也适用于图论问题。今天这两道题一道是二叉树的 DFS 经典难题另一道是图论的 DFS 入门模板题。它们的核心思想一脉相承但在应用场景上各有侧重。这篇博客会带你彻底搞懂它们的解题思路、代码实现和背后的通用模板看完就能直接上手一、二叉树中的最大路径和困难 题目描述给定一个非空二叉树返回其最大路径和。路径被定义为一条从树中任意节点出发沿父节点 - 子节点连接达到任意节点的序列。该路径至少包含一个节点且不一定经过根节点。 核心思路后序 DFS这道题的关键在于理解 “路径” 的定义路径可以从任意节点出发到任意节点结束但不能分叉。也就是说在路径中只能有一个节点作为 “拐点”路径的最高点。我们的解法是使用后序遍历先计算左右子树的贡献再处理当前节点。定义递归函数dfs(node)返回以node为起点向其子树延伸的最大路径和只能选左或右不能同时选。更新全局最大值在递归过程中计算以当前节点为 “拐点” 的路径和node.val leftContribution rightContribution并更新全局最大值。✅ 完整 AC 代码java运行/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { // 全局变量记录最大路径和初始值设为负无穷 private int maxSum Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return maxSum; } /** * 返回以 node 为起点向其子树延伸的最大路径和 * 同时更新全局最大路径和 */ private int dfs(TreeNode node) { if (node null) { return 0; } // 递归计算左右子树的贡献若为负则取0不选 int leftContribution Math.max(dfs(node.left), 0); int rightContribution Math.max(dfs(node.right), 0); // 以当前节点为拐点的路径和更新全局最大值 int currentPathSum node.val leftContribution rightContribution; maxSum Math.max(maxSum, currentPathSum); // 返回当前节点向父节点的贡献只能选左或右 return node.val Math.max(leftContribution, rightContribution); } } 关键细节解析为什么要取Math.max(dfs(...), 0)如果子树的贡献是负数那么选择不经过这个子树贡献为 0会更好。currentPathSum和return的区别currentPathSum是以当前节点为拐点的路径和可以同时包含左右子树用来更新全局最大值。return的值是向父节点传递的贡献只能包含当前节点 左 / 右子树中的一条路径因为路径不能分叉。二、岛屿数量中等 题目描述给你一个由1陆地和0水组成的二维网格计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。 核心思路图的 DFS / Flood Fill这道题是图的 DFS入门模板题核心思想是 “染色”遍历整个网格遇到未访问的陆地1说明发现了一个新岛屿。启动 DFS从这个陆地出发向上下左右四个方向递归搜索。标记已访问在 DFS 过程中将访问过的陆地标记为0水避免重复计算。岛屿计数每启动一次 DFS岛屿数量 1。✅ 完整 AC 代码java运行class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int count 0; int rows grid.length; int cols grid[0].length; // 遍历整个网格 for (int i 0; i rows; i) { for (int j 0; j cols; j) { // 遇到未访问的陆地岛屿数量1并启动DFS染色 if (grid[i][j] 1) { count; dfs(grid, i, j, rows, cols); } } } return count; } /** * DFS染色将(i,j)及其连通的陆地标记为0 */ private void dfs(char[][] grid, int i, int j, int rows, int cols) { // 越界判断或遇到水/已访问的陆地直接返回 if (i 0 || i rows || j 0 || j cols || grid[i][j] 0) { return; } // 标记为已访问染色 grid[i][j] 0; // 向上下左右四个方向递归 dfs(grid, i - 1, j, rows, cols); // 上 dfs(grid, i 1, j, rows, cols); // 下 dfs(grid, i, j - 1, rows, cols); // 左 dfs(grid, i, j 1, rows, cols); // 右 } } 关键细节解析染色法直接修改原数组将访问过的1改为0无需额外空间记录访问状态空间复杂度为 O (1)不算递归栈。边界判断在 DFS 入口处统一判断越界或遇到水逻辑更清晰。时间复杂度每个单元格最多被访问一次时间复杂度为 O (M*N)其中 M、N 为网格的行数和列数。 两道题核心思想对比表格题目数据结构DFS 类型核心技巧最大路径和二叉树后序 DFS全局变量记录最大值区分 “拐点路径和” 与 “向父节点的贡献”岛屿数量二维网格图Flood Fill DFS染色法标记已访问避免重复计算连通分量结语这两道题是 DFS 思想的绝佳范例最大路径和教你如何利用后序遍历在递归过程中同时更新全局状态。岛屿数量教你如何将 DFS 应用到图论问题中解决连通分量计数。