LeetCode 124 二叉树中的最大路径和：python3 题解

题目链接：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)

进一步的讲解：对于一个

1.    / 根节点 \
2. 左节点     右节点

复制代码

这样的结构，我们枚举它在二叉树的最大路径中，可能起到的作用。
具体的，我们可能取用 根节点-左节点-[左节点的子节点…] 或 根节点-右节点-[右节点的子节点…] 或 根节点 这样的部分，根节点如果有父节点的话，这一部分可以用来组成 父节点-根节点-[根节点的子节点…] 这样的最大路径。
另一方面，我们也可能取用 左节点→根节点→右节点 这样的结构，此时，路径可能是 […左节点的子节点]-左节点-根节点-右节点-[右节点的子节点…] 。
以下的 max_gain 函数，就分别枚举了这两种情况。

1. # 引入类型提示，虽然 LeetCode 环境通常已内置，但为了代码完整性保留
2. from typing import Optional
4. # 二叉树节点定义 (LeetCode 模板)
5. class TreeNode:
6.     def __init__(self, val=0, left=None, right=None):
7.         self.val = val
8.         self.left = left
9.         self.right = right
11. class Solution:
12.     def maxPathSum(self, root: Optional[TreeNode]) -> int:
13.         # 初始化全局最大路径和。
14.         # 注意：题目提示节点值最小为 -1000，所以初始值设为负无穷，
15.         # 确保即使树中只有一个负数节点，也能正确更新。
16.         self.max_sum = float('-inf')
17.         
18.         # 定义内部递归函数
19.         def max_gain(node: Optional[TreeNode]) -> int:
20.             """
21.             计算以 node 为起点的单侧最大路径贡献值。
22.             同时在这个过程中更新全局最大路径和 self.max_sum。
23.             """
24.             # 1. 终止条件：空节点贡献为 0
25.             if not node:
26.                 return 0
27.             
28.             # 2. 递归计算左右子树的最大贡献值
29.             # 如果子树的贡献值是负数，我们选择不走该子树（即贡献为 0）
30.             # max(0, ...) 是本题处理负数节点的关键
31.             left_gain = max(max_gain(node.left), 0)
32.             right_gain = max(max_gain(node.right), 0)
33.             
34.             # 3. 计算以当前 node 为“最高点”（转折点）的路径和
35.             # 这条路径连接了左子树、当前节点、右子树
36.             # 这条路径是“封闭”的，不能向上延伸，但可以用来更新全局最大值
37.             current_path_sum = node.val + left_gain + right_gain
38.             
39.             # 更新全局最大路径和
40.             self.max_sum = max(self.max_sum, current_path_sum)
41.             
42.             # 4. 返回当前节点能给父节点提供的最大贡献值
43.             # 父节点只能选择左边或右边其中一条路延伸，不能都要（否则分叉）
44.             return node.val + max(left_gain, right_gain)
45.         
46.         # 启动递归
47.         max_gain(root)
48.         
49.         # 返回最终计算出的最大路径和
50.         return self.max_sum

复制代码

4. 示例 walkthrough (以示例 2 为例)

输入: root = [-10, 9, 20, null, null, 15, 7]
树结构如下：

1.       -10
2.       /  \
3.      9   20
4.          / \
5.        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）。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！