LeetCode 题解工作台
二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。 示例 1： 输入： root = […
4
题型
8
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
我们思考二叉树递归问题的经典套路： 1. 终止条件（何时终止递归）
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
解题思路
方法一：递归
我们思考二叉树递归问题的经典套路：
- 终止条件（何时终止递归）
- 递归处理左右子树
- 合并左右子树的计算结果
对于本题，我们设计一个函数 ，它返回以 为根节点的二叉树的最大路径和。
函数 的执行逻辑如下：
如果 不存在，那么 返回 ；
否则，我们递归计算 的左子树和右子树的最大路径和，分别记为 和 。如果 小于 ，那么我们将其置为 ，同理，如果 小于 ，那么我们将其置为 。
然后，我们用 更新答案。最后，函数返回 。
在主函数中，我们调用 ，即可得到每个节点的最大路径和，其中的最大值即为答案。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# Definition for a binary tree node.
# 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:
def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0
left = max(0, dfs(root.left))
right = max(0, dfs(root.right))
nonlocal ans
ans = max(ans, root.val + left + right)
return root.val + max(left, right)
ans = -inf
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you account for negative node values when calculating the maximum path sum?
- question_mark
Can you explain how your DFS approach propagates maximum path contributions to the parent nodes?
- question_mark
Will you update the global maximum at each node correctly to include paths crossing through the node?
常见陷阱
外企场景- error
Forgetting to ignore negative subtree contributions when extending paths to parent nodes, leading to lower sums.
- error
Updating the global maximum only with single child contributions and missing paths through the current node.
- error
Confusing path extension to parent versus path sum including current node, which can incorrectly omit optimal paths.
进阶变体
外企场景- arrow_right_alt
Find maximum path sum where path must start and end at leaf nodes only.
- arrow_right_alt
Compute the maximum sum path in a binary tree constrained to paths of length at most k edges.
- arrow_right_alt
Determine the maximum path sum in a binary tree when nodes can be revisited at most once.