题目链接：124. 二叉树中的最大路径和
目录
- 1. 题目含义与核心难点
- 2. 解题思路分析
- 思路一：暴力枚举（不可行）
- 思路二：递归分解（后序遍历 DFS）—— 推荐解法
- 算法步骤
- 3. 代码实现 (Python 3)
- 4. 示例 walkthrough (以示例 2 为例)
- 5. 复杂度分析
- 6. 其他解法讨论
- 7. 总结与技巧
1. 题目含义与核心难点
题目重述
给定一个二叉树，我们需要找到一条路径，使得这条路径上所有节点的值之和最大。
- 路径定义：节点序列，相邻节点有边连接，每个节点最多出现一次。
- 起点与终点：路径可以在树的任意位置开始和结束，不一定经过根节点。
- 至少一个节点：路径不能为空。
核心难点
这道题的难点在于路径的走向。
- 不一定要经过根节点：这意味着我们不能简单地计算“从根节点出发的最大路径”，因为最大路径可能完全位于左子树或右子树中。
- 路径不能分叉：在二叉树中，一个节点最多有两个子节点。如果一条路径经过某个节点，它要么是从父节点下来再往一个子节点去（单臂），要么是从左子节点上来经过该节点再去右子节点（拱形）。它不能同时连接父节点、左子节点和右子节点（那样就分叉了，不是路径）。
2. 解题思路分析
思路一：暴力枚举（不可行）
最直观的想法是枚举所有可能的路径，计算它们的和，然后取最大值。
- 问题：二叉树中可能的路径数量是指数级的，暴力枚举会导致超时（Time Limit Exceeded）。
- 结论：我们需要一种更高效的方法，最好只遍历树一次。
思路二：递归分解（后序遍历 DFS）—— 推荐解法
我们需要在遍历树的过程中，动态地计算并更新最大路径和。这里有一个非常关键的概念区分：“贡献值” 与 “最大路径和”。
对于树中的任意一个节点 node，以它为“最高点”（即路径的转折点或端点）的路径有两种情况：
- 作为“拱形”路径的顶点：
- 路径形式：左子树某节点 -> ... -> node.left -> node -> node.right -> ... -> 右子树某节点
- 这种路径不能再向上延伸给 node 的父节点，因为它已经用了 node 的左右两个接口。
- 这种路径的和可以用来更新全局最大路径和。
- 计算公式：node.val + 左子树最大贡献 + 右子树最大贡献
- 作为“单臂”路径的一部分（向上贡献）：
- 路径形式：node -> node.left 或者 node -> node.right
- 这种路径可以延伸给 node 的父节点，因为只用了 node 的一个接口（或者作为端点）。
- 这个值需要返回给上一层递归调用。
- 计算公式：node.val + max(左子树最大贡献，右子树最大贡献)
关键细节：负数处理
如果子树返回的“最大贡献值”是负数，我们要不要加上它？
- 答案：不要。
- 理由：如果左子树的最大贡献是 -5，加上它只会让总和变小。我们可以选择“不走左边”，即贡献为 0。
- 操作：gain = max(0, recursive_call)
算法步骤
- 初始化一个全局变量 max_sum，记录遍历过程中遇到的最大路径和。初始值设为负无穷（因为节点值可能全为负）。
- 定义一个递归函数 max_gain(node)：
- 终止条件：如果 node 为空，返回 0。
- 递归计算：
- 计算左子树的最大贡献 left_gain（如果是负数则取 0）。
- 计算右子树的最大贡献 right_gain（如果是负数则取 0）。
- 更新全局最大值：
- 当前节点作为“拱形”顶点的路径和为 node.val + left_gain + right_gain。
- 用这个值更新 max_sum。
- 返回贡献值：
- 返回 node.val + max(left_gain, right_gain) 给父节点使用。
- 调用递归函数处理根节点。
- 返回 max_sum。
3. 代码实现 (Python 3)
进一步的讲解：对于一个这样的结构，我们枚举它在二叉树的最大路径中，可能起到的作用。
具体的，我们可能取用 根节点-左节点-[左节点的子节点…] 或 根节点-右节点-[右节点的子节点…] 或 根节点 这样的部分，根节点如果有父节点的话，这一部分可以用来组成 父节点-根节点-[根节点的子节点…] 这样的最大路径。
另一方面，我们也可能取用 左节点→根节点→右节点 这样的结构，此时，路径可能是 […左节点的子节点]-左节点-根节点-右节点-[右节点的子节点…] 。
以下的 max_gain 函数，就分别枚举了这两种情况。- # 引入类型提示，虽然 LeetCode 环境通常已内置，但为了代码完整性保留
- from typing import Optional
- # 二叉树节点定义 (LeetCode 模板)
- class TreeNode:
- def __init__(self, val=0, left=None, right=None):
- self.val = val
- self.left = left
- self.right = right
- class Solution:
- def maxPathSum(self, root: Optional[TreeNode]) -> int:
- # 初始化全局最大路径和。
- # 注意：题目提示节点值最小为 -1000，所以初始值设为负无穷，
- # 确保即使树中只有一个负数节点，也能正确更新。
- self.max_sum = float('-inf')
-
- # 定义内部递归函数
- def max_gain(node: Optional[TreeNode]) -> int:
- """
- 计算以 node 为起点的单侧最大路径贡献值。
- 同时在这个过程中更新全局最大路径和 self.max_sum。
- """
- # 1. 终止条件：空节点贡献为 0
- if not node:
- return 0
-
- # 2. 递归计算左右子树的最大贡献值
- # 如果子树的贡献值是负数，我们选择不走该子树（即贡献为 0）
- # max(0, ...) 是本题处理负数节点的关键
- left_gain = max(max_gain(node.left), 0)
- right_gain = max(max_gain(node.right), 0)
-
- # 3. 计算以当前 node 为“最高点”（转折点）的路径和
- # 这条路径连接了左子树、当前节点、右子树
- # 这条路径是“封闭”的，不能向上延伸，但可以用来更新全局最大值
- current_path_sum = node.val + left_gain + right_gain
-
- # 更新全局最大路径和
- self.max_sum = max(self.max_sum, current_path_sum)
-
- # 4. 返回当前节点能给父节点提供的最大贡献值
- # 父节点只能选择左边或右边其中一条路延伸，不能都要（否则分叉）
- return node.val + max(left_gain, right_gain)
-
- # 启动递归
- max_gain(root)
-
- # 返回最终计算出的最大路径和
- return self.max_sum
输入: root = [-10, 9, 20, null, null, 15, 7]
树结构如下：执行过程 (后序遍历：左 -> 右 -> 根)：
- 节点 9 (叶子):
- 左贡献 0, 右贡献 0。
- 当前路径和：9 + 0 + 0 = 9。更新 max_sum = 9。
- 返回给父节点 (-10) 的贡献：9 + max(0, 0) = 9。
- 节点 15 (叶子):
- 左贡献 0, 右贡献 0。
- 当前路径和：15。更新 max_sum = 15。
- 返回给父节点 (20) 的贡献：15。
- 节点 7 (叶子):
- 左贡献 0, 右贡献 0。
- 当前路径和：7。max_sum 保持 15。
- 返回给父节点 (20) 的贡献：7。
- 节点 20:
- 左贡献 (来自 15) = 15。
- 右贡献 (来自 7) = 7。
- 当前路径和 (拱形)：20 + 15 + 7 = 42。更新 max_sum = 42。
- 返回给父节点 (-10) 的贡献：20 + max(15, 7) = 35。
- 注意：这里返回 35 而不是 42，因为向上只能选一边。
- 节点 -10 (根):
- 左贡献 (来自 9) = 9。
- 右贡献 (来自 20) = 35。
- 当前路径和 (拱形)：-10 + 9 + 35 = 34。max_sum 保持 42 (因为 42 > 34)。
- 返回给上层的贡献：-10 + max(9, 35) = 25。
最终结果: 42。
5. 复杂度分析
- 时间复杂度: \(O(N)\)
- 其中 \(N\) 是二叉树的节点数。
- 我们对每个节点只访问了一次（后序遍历），在每个节点上的操作都是常数时间的。
- 空间复杂度: \(O(H)\)
- 其中 \(H\) 是二叉树的高度。
- 这是递归调用栈的空间消耗。
- 最坏情况下（树退化为链表），\(H = N\)，空间复杂度为 \(O(N)\)。
- 最好情况下（完全平衡树），\(H = \log N\)，空间复杂度为 \(O(\log N)\)。
6. 其他解法讨论
虽然递归 DFS 是最优解，但了解其他思路有助于加深理解：
- 迭代法 (Iterative DFS):
- 思路：使用显式的栈（Stack）来模拟递归过程。需要记录节点的状态（是第一次访问还是第二次访问），以便在子节点处理完后处理当前节点（后序逻辑）。
- 缺点：代码实现比递归复杂得多，需要手动维护栈帧信息，容易出错。在 Python 中，由于递归深度限制，如果树非常深（例如 \(10^5\) 层），递归可能会爆栈（RecursionError），此时迭代法是必要的。但在本题 \(3 \times 10^4\) 的限制下，递归通常是安全的。
- 适用性：仅在树深度极大导致递归溢出时考虑。
- 动态规划 (DP on Tree):
- 思路：其实上述递归解法本质上就是树形 DP。每个节点的状态依赖于子节点的状态。
- 区别：没有本质区别，只是叫法不同。树形 DP 通常也是通过 DFS 实现的。
- 错误的贪心思路:
- 错误想法：从根节点开始，每次选左右子树中和更大的那边往下走。
- 为什么错：最大路径不一定经过根节点。例如示例 2 中，根节点是 -10，如果从根开始贪心，可能会忽略掉右子树内部 15->20->7 这条更大的路径。
7. 总结与技巧
- 区分“返回值”与“全局值”：这是解决此类树路径问题最核心的技巧。递归函数的返回值通常是“能向上延伸的最大值”，而全局变量记录“任意形状的最大值”。
- 负数剪枝：max(0, gain) 是处理节点值为负数时的标准操作，意味着“如果这条路是负收益，我就不走这条路”。
- 后序遍历：因为我们需要先知道子节点的信息，才能计算当前节点的信息，所以必须是后序（Left -> Right -> Root）。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
