Binary tree maximum path sum

Postorder: each node hands its parent its best downward gain, and checks the best path that bends through it.

The idea

Any path has one highest node where it bends: it comes up one side and goes down the other. So at every node, the best path bending there is left gain + node + right gain, where a gain is the best sum of a path going straight down from a child. A negative gain only hurts, so replace it with 0 (just do not extend that way). The node then returns node + the larger gain to its parent, because a path passing up through it can use only one side.

Code

private int best = int.MinValue;

public int MaxPathSum(TreeNode root) {
    Gain(root);
    return best;
}

private int Gain(TreeNode node) {
    if (node == null) return 0;
    int left = Math.Max(Gain(node.left), 0);
    int right = Math.Max(Gain(node.right), 0);
    best = Math.Max(best, left + node.val + right);
    return node.val + Math.Max(left, right);
}

Tips

• Start best at int.MinValue, not 0: a tree of all negative values still has an answer (its largest single node).
• Two different numbers per node is the key: the bent path (both sides) updates the answer, the one-sided gain is what the parent can use.

In the .NET library

A field (or a captured local in a local function) holds the running best. In C#, int arithmetic wraps silently on overflow; node values here are small, but wrap the sum in checked(...) when they might not be.