A path is a sequence of nodes connected by edges, each used at most once; it need not pass through the root. Return the maximum sum of values on any non-empty path.
Before you code
This is the diameter problem with weights. A path turns at some node and uses its best branch on each side. Values can be negative, so a branch can make a path worse.
Hints
gain(node)returns the best sum of a path that starts at node and goes down one side:node.val + max(0, gain(left), gain(right)).- At each node, the best path turning there is
node.val + max(0, gain(left)) + max(0, gain(right)). Record the maximum. - Initialize the record to negative infinity, not 0: a tree of all negative values still has a best path.
Production & complexity notes
When solving Binary tree maximum path sum on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Tree recursion patterns to reinforce the underlying pattern.
What it practices
The return-one-record-another shape, from Tree recursion patterns.