124. Binary Tree Maximum Path Sum

A path is any sequence of adjacent nodes, each used at most once, that need not pass through the root. Return the maximum sum of any non-empty path.

One post-order DFS returns each node's best downward gain. At each node, update the answer with node + left gain + right gain, but return only node + the better of the two (a path cannot fork when passed upward).

1function maxPathSum(root: TreeNode | null): number {
2  let best = -Infinity;
3  function gain(n: TreeNode | null): number {
4    if (!n) return 0;
5    const left = Math.max(0, gain(n.left));
6    const right = Math.max(0, gain(n.right));
7    best = Math.max(best, n.val + left + right);
8    return n.val + Math.max(left, right);
9  }
10  gain(root);
11  return best;
12}

best = -∞

tree

At -10: best gain from the left?

1 / 0

Space: play/pause · ←/→: step