Binary Tree Maximum Path Sum

Problem Return the maximum path sum in a binary tree: a path is any node sequence connected by edges, visiting each node at most once — it may start and end anywhere and need not pass through the root. Node values may be negative.

Input / Output

• Input: tree root. Output: max path sum.

Constraints

• Up to 3*10^4 nodes; values in [−1000, 1000]; O(n) single traversal expected.

Example

• [-10,9,20,null,null,15,7] → 42 (15 + 20 + 7); [2,-1] → 2.

Expected approach

• Post-order recursion with two quantities per node: (a) best DOWNWARD gain usable by the parent = node + max(0, leftGain, rightGain); (b) best path THROUGH the node = node + max(0,leftGain) + max(0,rightGain), folded into a global max. The clamp-to-zero (dropping negative subtrees) and the through-vs-downward distinction are the whole problem. O(n)/O(h). Standard escalations: return the actual path, count paths equal to the max, path sum between leaves only.