难度: Hard
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 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注意：本题与主站 124 题相同： https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
运行时间: 44 ms
内存: 21.0 MB
# 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: TreeNode) -> int:
ans = -float("Inf")
def dfs(node):
nonlocal ans
if not node: return 0
left = dfs(node.left)
right = dfs(node.right)
ans = max(ans, left + right + node.val)
return max(max(left, right) + node.val, 0)
dfs(root)
return ans
这个方法利用深度优先搜索（DFS）遍历二叉树的每个节点，同时计算以每个节点为顶点的最大路径和。对于每个节点，考虑两种情况：1.路径包括该节点及其左右子树；2.路径不包括子树，只有该节点自己。具体算法中，首先计算左右子树提供的最大贡献值，如果子树的贡献值为负，则认为不包括该子树的贡献。然后，更新全局的最大路径和，包括当前节点值以及左右子树的最大贡献。此外，函数返回到父节点的最大单边路径和，以便父节点计算其最大路径和时使用。这种方法确保我们计算了所有可能的路径，并在遍历过程中保存了最大值。
时间复杂度: O(n)
空间复杂度: O(n)
# 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: TreeNode) -> int:
ans = -float("Inf") # 初始化全局最大路径和为负无穷
def dfs(node):
nonlocal ans # 引用外部变量ans
if not node: return 0 # 如果节点为空，则返回0
left = dfs(node.left) # 计算左子树的最大贡献
right = dfs(node.right) # 计算右子树的最大贡献
ans = max(ans, left + right + node.val) # 更新最大路径和
return max(max(left, right) + node.val, 0) # 返回到父节点的最大单边路径和
dfs(root) # 从根节点开始深度优先搜索
return ans # 返回计算的最大路径和
在计算全局最大路径和时，考虑的是通过当前节点连接左右子树形成的完整路径，这可能包括左子树、当前节点、右子树。这种情况下，路径是不可能延伸到当前节点的父节点，因为这将形成一个分叉（非线性路径）。因此，当考虑到达父节点的最大路径时，我们只能选择左子树和右子树中的一个较大贡献加上当前节点的值，这样确保路径是连续的且没有分叉，适合向上延伸至树的其他部分。
如果节点的值为负数，它会减少从该节点延伸出的路径的总和。在计算该节点的最大贡献值时，如果左子树或右子树的贡献值加上当前节点的负值仍然小于零，那么这个贡献值不应被包括在内，因为它会减少到达该节点的父节点的最大路径和。在实际的dfs实现中，我们通过返回`max(max(left, right) + node.val, 0)`确保了贡献值为负时，不会影响到父节点的路径和。这意味着，即使当前节点的值为负，也只有当节点的贡献值能够提供正增益时才考虑这种贡献。
使用非局部变量`ans`可以使代码更加简洁，因为它允许在递归函数内直接更新全局最大路径和，而无需通过每个递归调用传递和返回这个值。这种方法的优点是减少了函数参数的复杂性，使得递归结构更清晰。然而，这也意味着函数的纯粹性（不依赖于外部状态）被破坏，这可能在多线程环境中引发问题，或者在需要多次调用同一函数但期望独立结果的情况下引起状态污染。此外，使用非局部变量使得函数的重用和测试变得更加困难。