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