LeetCode124：二叉树中的最大路径和

题目描述： 给定一个非空二叉树，返回其最大路径和。路径被定义为一条从树中任意节点出发，到达任意节点的一条序列。路径至少包含一个节点，且不需要经过根节点。

---

解题分析和主要思路

要理解并解决问题的关键在于弄清楚二叉树路径的特性：

路径可以从任意节点开始，到任何节点结束。路径可能不经过某些节点，也可能跨越多个子树。路径中不允许循环，因此路径上的父节点和子节点唯一相连。

最大路径和问题可以分解为两大子任务：

最大单边路径和：某节点的最大单边路径和。即从某节点延伸到一个方向（左子树或右子树）的最大和。最大跨节点路径和：某节点形成的跨左右子树的路径和，可能是最大路径和的候选值。

最终，我们需要选出全局最大路径和（单边路径和 + 跨越路径和）。

---

解法 1：递归DFS + 后序遍历

在后序遍历的过程中，自底向上计算每个节点的最大单边路径和和跨节点路径和：

对于每个节点： 递归计算其左子树和右子树的最大单边路径和。使用当前节点的值 + 左/右单边路径和（如果它们为正）得到当前跨节点路径的总和。更新全局最大路径和。返回以当前节点为根节点的最大单边路径和max(root.val + left, root.val + right)。 模板代码 class Solution { private int maxSum = Integer.MIN_VALUE; // 全局最大路径和 public int maxPathSum(TreeNode root) { dfs(root); // 递归后序遍历 return maxSum; } private int dfs(TreeNode root) { if (root == null) return 0; // 空节点返回 0（对路径贡献为零） // 后序遍历：递归计算左右子树的最大单边路径和 int left = Math.max(0, dfs(root.left)); // 如果子树路径和为负，则丢弃（取 0） int right = Math.max(0, dfs(root.right)); // 同上 // 跨越当前节点的最大路径和（包括左右子树路径） int localMaxPathSum = root.val + left + right; maxSum = Math.max(maxSum, localMaxPathSum); // 更新全局最大路径和 // 返回以当前节点为起点的最大单边路径和 return root.val + Math.max(left, right); } }

---

时间复杂度 O(N)：每个节点只会被访问一次（后序遍历）。O(H)：递归调用的栈空间，H 是树的高度。

---

解法 2：迭代法（基于后序遍历的非递归解法）

这个问题大多数情况下使用递归解决，因为深度优先搜索更契合于二叉树的结构。如果你想使用迭代法，则需基于「模拟后序遍历」实现栈的迭代式计算。

思路 使用一个栈对二叉树进行后序遍历（左右子树先分别入栈）。同时在栈中保存一个标记，标志该节点是否已被第二次访问。在真正访问节点时，计算其左右子树的最大单边路径和和跨节点路径和。

---

如何快速 AC？（关键优化点） 剪枝： 子树的路径和为负时，直接丢弃（返回 0），因为对最大路径和无益。全局变量： 利用全局变量存储最大路径和，无需额外数据结构。理解半路径和跨路径： 单边路径和（延伸性）与跨节点路径和（终止性）结合解决问题，减少思维复杂度。动态规划思想： 每个节点的问题可以被左右子树递归解决后合并成一个局部最优解（递归分治）。

---

经典变体题目 1. 543. 二叉树的直径

问题： 返回二叉树中两节点之间的路径长度（边数）的最大值。

解法分析

与 124 类似，只是求 最长路径经过的边数，而不是路径和值。

最大路径：使用左右子树深度之和。修改公式：直径 = 左子树高度 + 右子树高度。在后序遍历时，计算递归高度。 模板代码 class Solution { private int maxDiameter = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } private int depth(TreeNode root) { if (root == null) return 0; // base case int leftDepth = depth(root.left); int rightDepth = depth(root.right); // 更新直径：左右子树深度之和 maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth); // 返回节点的深度 return 1 + Math.max(leftDepth, rightDepth); } }

---

2. 路径的最小和

问题： 给定一个二叉树，找到从根节点到叶子节点路径和的最小值。

解法分析 使用 DFS 遍历所有的叶子节点，比较路径和。从根节点累加路径和，递归到叶子节点时更新最小值。 模板代码 class Solution { private int minSum = Integer.MAX_VALUE; public int minPathSum(TreeNode root) { if (root == null) return 0; dfs(root, 0); return minSum; } private void dfs(TreeNode root, int currentSum) { if (root == null) return; currentSum += root.val; // 如果是叶子节点，更新最小路径和 if (root.left == null && root.right == null) { minSum = Math.min(minSum, currentSum); } // 递归子树 dfs(root.left, currentSum); dfs(root.right, currentSum); } }

---

3. 带路径限制的最大路径和

问题： 求路径中不能超过 k 个节点的最大路径和。

解法分析

动态规划扩展，限制路径长度：

增加一个参数维护路径长度。当路径长度超过 k 时停止递归。 模板代码 class Solution { private int maxSum = Integer.MIN_VALUE; public int maxPathSumWithLimit(TreeNode root, int k) { dfs(root, k, 0); return maxSum; } private void dfs(TreeNode root, int k, int steps) { if (root == null || steps > k) return; int left = Math.max(0, dfs(root.left, k, steps + 1)); int right = Math.max(0, dfs(root.right, k, steps + 1)); // 更新最大路径和 maxSum = Math.max(maxSum, root.val + left + right); return root.val + Math.max(left, right); } }

---

4. 找到路径的具体节点序列

问题： 返回最大路径和对应的路径节点序列。

解法分析 修改递归，记录路径： 在返回递归路径和的同时，通过列表记录路径。 对于左右子树，比较路径和，并选择更大的路径更新序列。

---

5. 求二叉树某节点到叶子的最大路径和

问题： 给定一个起点节点，求从该节点到叶节点的最大路径和。

解法分析 从给定的根节点开始递归，累加单边路径和到叶节点。

---

总结 124 的核心解法是递归 + 全局更新，后序遍历是关键，将问题分解为当前节点 + 左右子树最优解。变体题目基于这一思想扩展，通过增加路径限制、记录顺序或特殊规则处理。模板化递归通常是快速 AC 的手段，尤其对裁剪条件优化能显著提升效率。