binary-tree-max-path-sum.ts

import { TreeNode } from "../lib/tree-node.js";

/**
 * 124. Binary Tree Maximum Path Sum  (Hard)
 * Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/
 *
 * A path is any sequence of nodes connected by edges; it need not pass through
 * the root. Return the maximum sum of node values along any such path.
 *
 * Example:
 *   Input:  [-10, 9, 20, null, null, 15, 7]
 *   Output: 42           // 15 -> 20 -> 7
 *
 * Approach:
 *   Post-order DFS returning the best downward gain from a node (its value plus
 *   the larger of its two child gains, floored at 0 to ignore negative
 *   branches). At each node the best path THROUGH it is value + leftGain +
 *   rightGain; track the global maximum of those while returning only the single
 *   branch upward.
 *
 * Time:  O(n)
 * Space: O(h)  — recursion stack.
 */
export function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;

  function gain(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(gain(node.left), 0);
    const right = Math.max(gain(node.right), 0);
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  }

  gain(root);
  return best;
}