Untitled

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = -float('inf')
        def maxPath(node):
            if node:
                l, r = max(maxPath(node.left), 0), max(maxPath(node.right), 0)
                self.ans = max(self.ans, l+r+node.val)
                return max(l, r) + node.val
            return 0
        maxPath(root)
        return self.ans