124. Binary Tree Maximum Path Sum

Loading...LeetCode

和 Q968 的思路有点共通，都是 postorder 从叶子节点开始递归传递局部解（子树解），一直到root为止，不同的是这边最终要的并非 root 解，而是全局过程中可能的最优情况（max sum）。

968. Binary Tree Cameras

# 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 __init__(self):
        self.MPS = -0x7FFFFFFF
    @functools.lru_cache()
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxSucceed(root)
        return self.MPS
        
    def maxSucceed(self, root):
        if not root: return 0 # 到头了，没有值，返回0
    
        ## case1: 从左子树走，继承的最大sum，负数的话就直接不走了
        goLeft = max([self.maxSucceed(root.left), 0])
        ## case2: 右子树同理
        goRight = max([self.maxSucceed(root.right), 0])
        ## case3: 直接以当前node为根，穿过node的最大sum，是可能的答案
        goRoot = goLeft + goRight + root.val
        self.MPS = max([self.MPS, goRoot])
        
        return root.val + max([goLeft, goRight])