Binary Tree Maximum Path Sum

Hard

Problem

A path is any sequence of connected nodes (going up and then down at most once), with no node repeated; it need not pass through the root. Return the largest sum of any non-empty path. Values can be negative.

Example 1

Input:  [1, 2, 3]
Output: 6

Example 2

Input:  [-10, 9, 20, null, null, 15, 7]
Output: 42

15 → 20 → 7.

Test cases

Case 1

Input:    [1,2,3]
Expected: 6

Case 2

Input:    [-10,9,20,null,null,15,7]
Expected: 42

Case 3

Input:    [-3]
Expected: -3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Post-order: return best downward gain, update global best

Time O(n)Space O(h)

At each node, the path that bends here is val + left gain + right gain (gains clipped at 0). Only one side can continue upward, so return val + max(gain).

function maxPathSum(root) {
let best = -Infinity;
const gain = (node) => {
if (!node) return 0;
const l = Math.max(0, gain(node.left));
const r = Math.max(0, gain(node.right));
best = Math.max(best, node.val + l + r);
return node.val + Math.max(l, r);
};
gain(root);
return best;
}

Same shape as diameter: "answer through this node" differs from "value returned to parent".