二叉树的最大路径和

Leetcode Link: 124. 二叉树中的最大路径和 - 力扣（LeetCode） (leetcode-cn.com)

题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

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

给你一个二叉树的根节点 root ，返回其 最大路径和 。

解法一

思路：思路同二叉树的直径。 对于满足要求的路径和，它的路径一定会经过某个子树的根节点。 那么对于当前节点 cur，其可能的最大路径和，只可能有如下 4 个情况

1. 自己就是最大的，即 cur.val 最大
2. 自己+左子树最大，即 cur.val+left 最大
3. 自己+右子树最大，即 cur.val+right 最大
4. 横跨自己的路径和最大，即 cur.val+left+right 最大

难点

思考清楚递归函数的的返回值和答案之间的区别

题解：

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 注意定义方法
        max_val =  -float('inf')
        
        def recur(cur):
            nonlocal max_val
            if not cur:
                return None
            
            left = recur(cur.left)
            right = recur(cur.right) 
 
            sum1 = cur.val
            sum2 = (cur.val + left) if left else cur.val
            sum3 = (cur.val + right) if right else cur.val
            sum4 = sum2 + sum3 - sum1 # cur.val + left + right, 这样写避免判断left和right为None
            max_val = max(sum1, sum2, sum3, sum4, max_val)
 
            # 只是不能返回横跨当前节点的路径和，如果当前节点sum1 > max(sum2, sum3)，则需要返回sum1
            # 开始我错在只考虑单边路径和，返回的是 max(sum2, sum3)
            return max(sum2, sum3, sum1)
 
        recur(root)
        return max_val
            

---

二刷自己写的答案

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = -float('inf')
 
        # 返回*含有*当前节点的最大路径和，但是不一定是结果
        def dfs(node):
            nonlocal res
            if not node:
                return 0
 
            left = dfs(node.left)
            right = dfs(node.right)
            # 新结果只可能出现在后面4中。
            res = max(res, node.val, left+node.val, right+node.val, left+right+node.val)
            # 这里一定不能返回 left+right+node.val，和父节点无法组成路径。
            return max(node.val, node.val+left, node.val+right) 
        
        dfs(root)
        return res

启发和联系

• 相关题目： 二叉树的直径
• 定义最小值 max_val = -float('inf')
• 定义最大值 max_val = float('inf')
• max(a, None) 会报错