124. 二叉树中的最大路径和
class Solution: def maxPathSum(self, root: TreeNode) -> int: """ 解决这题的主要思路是分断考虑+递归 最大路径和的取得有三种情况: 1. 当前root结点和左右贡献的和,注意,左右贡献为负数就初始化为0 2. 当前root结点不参与路径,左子树贡献最大路径和 3. 当前root结点不参与路径,右子树贡献最大路径和 """ res = float("-inf") def dfs(root): nonlocal res # 定义嵌套函数空间中的变量 if not root: return 0 left_max_val = max(0, dfs(root.left)) # 计算左子树的最大路径和 right_max_val = max(0, dfs(root.right)) # 计算右子树的最大路径和 cur_max_val = root.val + left_max_val + right_max_val # 当前root为根结点的最大路径和 res = max(res, cur_max_val) # 此处最重要,判断当前root为根节点的路径和大,还是上一层的路径和大 return root.val + max(left_max_val, right_max_val) """ 这里之所以这样返回值,是因为如果以root的上层结点为根节点,那么当前root结点就只能取一条路径, 要么root -> left, 要么root -> right。例如图中,若当前root = 20,那么root对于上层结点-10的贡献 就只能是20->15或者20->7,从而构成9 -> -10 -> 20 -> 15或者9 -> -10 -> 20 -> 7。所以dfs(root = 20)的 返回值就只能是root.val + max(left_max_val, right_max_val)。 """ dfs(root) return res