Binary Tree Maximum Path Sum

The problem

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

Function: def maxPathSum(root):

Example input (a JSON list of arguments): [[-10, 9, 20, null, null, 15, 7]]
Expected output: 42

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. A path passed to a parent can use at most one child branch, while a path ending at the current node may combine both.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def maxPathSum(root):
    best=-float('inf')
    def gain(node):
        nonlocal best
        if not node: return 0
        l=max(0,gain(node.left)); r=max(0,gain(node.right)); best=max(best,node.val+l+r)
        return node.val+max(l,r)
    gain(root); return best

Why it works

A path passed to a parent can use at most one child branch, while a path ending at the current node may combine both. Ignore negative child gains, but initialize the global answer below all real node values.

Complexity: O(n) time / O(h) space.

Time: O(n) time · Space: O(h) space