124.二叉树中的最大路径和 python

题目

题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 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 * $10^4$]
-1000 <= Node.val <= 1000

题解

为了找到二叉树中的最大路径和，我们可以使用递归的方法来遍历树，并在每个节点计算两种类型的路径和：

1. 穿过该节点的路径的最大和：这条路径可以从左子树延伸到右子树，并且必须包含当前节点。这是用来更新全局最大路径和的。
2. 从该节点出发的最大路径和：这条路径只能选择左子树或右子树之一，因为路径不能分叉。这是返回给父节点使用的值。

解决方案步骤

1. 定义辅助函数：创建一个递归辅助函数 max_gain(node) 来计算从某个节点出发的最大路径和。这个函数会递归地处理左右子树，并计算通过该节点的最大路径和。
2. 更新全局最大路径和：对于每个节点，计算穿过该节点的最大路径和（即左子树的最大增益 + 右子树的最大增益 + 节点值），并尝试更新全局最大路径和。
3. 返回结果：辅助函数返回的是从该节点出发的最大路径和（不包括同时向左和向右的情况），以确保递归调用的一致性。

Python 实现

下面是具体的实现代码：

def maxPathSum(root: TreeNode) -> int:max_sum = float('-inf')def max_gain(node):nonlocal max_sumif not node:return 0# 递归计算左右子树的最大贡献值left_gain = max(max_gain(node.left), 0)right_gain = max(max_gain(node.right), 0)# 更新全局最大路径和price_newpath = node.val + left_gain + right_gainmax_sum = max(max_sum, price_newpath)# 返回从该节点出发的最大路径和return node.val + max(left_gain, right_gain)max_gain(root)return max_sum

解释

• max_gain(node) 函数：这是一个递归函数，用于计算从给定节点出发的最大路径和。如果节点为空，则返回 0。
• left_gain 和 right_gain：分别计算左子树和右子树的最大贡献值。如果贡献值为负数，则取 0，表示不选择该子树。
• price_newpath：计算穿过当前节点的最大路径和，并更新全局最大路径和 max_sum。
• 返回值：返回从当前节点出发的最大路径和，注意这里只考虑选择左子树或右子树之一，以避免路径分叉。

这种方法的时间复杂度为 O(n)，其中 n 是树中节点的数量，因为我们只需要遍历每个节点一次。空间复杂度取决于递归栈的深度，在最坏情况下是 O(n)（对于完全不平衡的树），但在平均情况下是 O(log n)（对于平衡树）。这种解决方案能够有效地找出二叉树中的最大路径和。

提交结果