Hard

Binary Tree Maximum Path Sum

067

Given a binary tree encoded as level-order with -100000 as null, return the maximum path sum.

EXAMPLES

Example 1

Input
{
  "root": [
    1,
    2,
    3
  ]
}

Output
6

FUNCTION SHAPE

root: intArray→int

SOLUTION NOTE

The path can be "V-shaped". If dfs(root) returns the max straight-chain path including root, we update res with: best_left + root.val + best_right. Every node could be the top of the optimal V. Use max(0, path) since paths can be negative.

Reveal reference solution +

pythonREFERENCE

def maxPathSum(self, root: Optional[TreeNode]) -> int:
    res = float('-inf')

    # Returns max NON-EMPTY path that passes through/starts at root
    def dfs(root):
        if not root:
            return 0
        nonlocal res
        left_max = dfs(root.left)
        right_max = dfs(root.right)

        # Update global res with V-shaped path through this node
        res = max(res, max(0, left_max) + root.val + max(0, right_max))

        # Return best single-direction path including this node
        return max(root.val, root.val + left_max, root.val + right_max)

    dfs(root)
    return res

TimeO(n)

SpaceO(h)

Open on LeetCode ↗