#Leetcode 124

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def tree(root):
            if not root:
                return 0, -sys.maxsize-1
            
            left_val, total_left_val = tree(root.left)
            right_val, total_right_val = tree(root.right)

            curr = root.val + max(0, left_val) + max(0, right_val)
            return max(left_val, right_val, 0) + root.val, max(curr, total_left_val, total_right_val)
        
        _, ans = tree(root)
        return ans