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

前言

DFS（深度优先搜索）是算法面试的核心技能，它不仅适用于二叉树，也适用于图论问题。今天这两道题，一道是二叉树的 DFS 经典难题，另一道是图论的 DFS 入门模板题。它们的核心思想一脉相承，但在应用场景上各有侧重。

这篇博客会带你彻底搞懂它们的解题思路、代码实现和背后的通用模板，看完就能直接上手！

一、二叉树中的最大路径和（困难）

🎯 题目描述

给定一个非空二叉树，返回其最大路径和。路径被定义为一条从树中任意节点出发，沿父节点 - 子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

💡 核心思路（后序 DFS）

这道题的关键在于理解 “路径” 的定义：

• 路径可以从任意节点出发，到任意节点结束，但不能分叉。
• 也就是说，在路径中，只能有一个节点作为 “拐点”（路径的最高点）。

我们的解法是：

1. 使用后序遍历：先计算左右子树的贡献，再处理当前节点。
2. 定义递归函数dfs(node)：返回以node为起点，向其子树延伸的最大路径和（只能选左或右，不能同时选）。
3. 更新全局最大值：在递归过程中，计算以当前节点为 “拐点” 的路径和（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); } }

📝 关键细节解析

1. 为什么要取Math.max(dfs(...), 0)？如果子树的贡献是负数，那么选择不经过这个子树（贡献为 0）会更好。
2. currentPathSum和return的区别？
   • currentPathSum是以当前节点为拐点的路径和，可以同时包含左右子树，用来更新全局最大值。
   • return的值是向父节点传递的贡献，只能包含当前节点 + 左 / 右子树中的一条路径，因为路径不能分叉。

二、岛屿数量（中等）

🎯 题目描述

给你一个由'1'（陆地）和'0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。

💡 核心思路（图的 DFS / Flood Fill）

这道题是图的 DFS入门模板题，核心思想是 “染色”：

1. 遍历整个网格：遇到未访问的陆地（'1'），说明发现了一个新岛屿。
2. 启动 DFS：从这个陆地出发，向上下左右四个方向递归搜索。
3. 标记已访问：在 DFS 过程中，将访问过的陆地标记为'0'（水），避免重复计算。
4. 岛屿计数：每启动一次 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. 染色法：直接修改原数组，将访问过的'1'改为'0'，无需额外空间记录访问状态，空间复杂度为 O (1)（不算递归栈）。
2. 边界判断：在 DFS 入口处统一判断越界或遇到水，逻辑更清晰。
3. 时间复杂度：每个单元格最多被访问一次，时间复杂度为 O (M*N)，其中 M、N 为网格的行数和列数。

🎯 两道题核心思想对比

表格

结语

这两道题是 DFS 思想的绝佳范例：

• 最大路径和教你如何利用后序遍历，在递归过程中同时更新全局状态。
• 岛屿数量教你如何将 DFS 应用到图论问题中，解决连通分量计数。