Maximum Path Sum Through Any Path

hard tree dfs dp

Problem

A path is any sequence of nodes connected by parent-child edges; it can start and end anywhere and need not pass through the root. Return the largest sum along any such path.

For each node, the best path that passes through it equals node.val + max(0, gain(left)) + max(0, gain(right)). The best path that continues upward from this node uses only one side: gain(node) = node.val + max(0, max(gain(left), gain(right))). Track a global best while computing gains in a single post-order DFS.

Inputlevel-order: [-10, 9, 20, _, _, 15, 7]

Output42

Path 15 → 20 → 7 sums to 42.

level-order ('_' for null)

def max_path_sum(root):
    best = [float("-inf")]
    def gain(node):
        if node is None: return 0
        l = max(0, gain(node.left))
        r = max(0, gain(node.right))
        best[0] = max(best[0], node.val + l + r)
        return node.val + max(l, r)
    gain(root)
    return best[0]

function maxPathSum(root) {
  let best = -Infinity;
  function 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;
}

class Solution {
    int best = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) { gain(root); return best; }
    int gain(TreeNode node) {
        if (node == null) return 0;
        int l = Math.max(0, gain(node.left));
        int r = Math.max(0, gain(node.right));
        best = Math.max(best, node.val + l + r);
        return node.val + Math.max(l, r);
    }
}

int best = INT_MIN;
int gain(TreeNode* node) {
    if (!node) return 0;
    int l = max(0, gain(node->left));
    int r = max(0, gain(node->right));
    best = max(best, node->val + l + r);
    return node->val + max(l, r);
}

Time: O(n) Space: O(h) recursion depth