124. Binary Tree Maximum Path Sum

Problem¶

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

Solve¶

Dynamic programming on Tree¶

I hate it when I can’t control how TreeNode work, my first approach to to populate all TreeNode with it maxPath (the max value of path that contain its self as the end node).

We calculate base on this formula:

• maxPath(root) = Max(0, root.val) + max(maxPath(left), maxPath(right))

After that, we try to find the Maximum Path Sum by checking all possible TreeNode

• maxPathSum(root) = pathOnlyIn(Root) = max(pathOnlyIn(Left) , pathOnlyIn(Right) , pathGoTrough(Root))
• pathGoTrough(Root) = maxPath(left) + maxPath(right) + root.val
• pathOnlyIn(None) = 0
• pathGoTrough(None) = Not define

But, I can’t just adding the left.maxPath, right.maxPath; so here is the code that combining both in one loop

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def helper(root):
            if root is None:
                return 0, -100000

            maxLeftPath, onlyLeftMax = helper(root.left)
            maxRightPath, onlyRightMax = helper(root.right)

            maxRootPath = max(root.val, root.val + max(maxLeftPath, maxRightPath))

            onlyRootMax = root.val + max(0, maxLeftPath) + max(0, maxRightPath)

            maxPathSum = max(onlyLeftMax, onlyRightMax, onlyRootMax)

            return maxRootPath, maxPathSum

        _, maxPathSum = helper(root) 

        return maxPathSum