Binary Tree Maximum Path Sum
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
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".