binary_tree_max_path_sum.py

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_path_sum = float('-inf') # force update at least once
        
        def recurse(root: TreeNode) -> int:
            if not root: return 0 # base case
            left_sum, right_sum = max(0, recurse(root.left)), max(0, recurse(root.right)) # only care about positive gains
            self.max_path_sum = max(self.max_path_sum, left_sum + root.val + right_sum)
            return root.val + max(left_sum, right_sum)
        
        recurse(root)
        return self.max_path_sum