Binary Tree Maximum Path Sum

Problem: Binary Tree Maximum Path Sum

The problem is quite similar to solving diameter in a tree. The difference is what we want might not be a diameter due to existence of negative numbers and the path are weighted.

Code in Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            lp = rp = 0
            ld = rd = None
            if node.left:
                lp, ld = dfs(node.left)
                lp = max(lp, 0)
            if node.right:
                rp, rd = dfs(node.right)
                rp = max(rp, 0)
            return node.val + max(lp, rp), max(node.val + lp + rp, ld, rd)
        if root:
            return dfs(root)[1]
        return 0