Binary Tree Maximum Path Sum
Problem
A path is any sequence of nodes connected by edges where each node appears at most once; it need not pass through the root. Return the largest possible sum of node values along any non-empty path. Node values may be negative.
Examples
Constraints
- • 1 <= number of nodes <= 3 * 10^4
- • -1000 <= Node.val <= 1000
Hints & approach
Hint 1
This is the diameter idea with sums instead of edge counts.
Hint 2
A path can bend at one node, but what you report upward to a parent must be a single downward branch.
Hint 3
A branch with a negative sum is better dropped, so clamp child gains at 0.
Approachtry the hints first
Define gain(node) as the best sum of a downward path starting at node. Compute left = max(gain(left), 0) and right = max(gain(right), 0). The best path bending at this node is val + left + right, so update a global maximum with it. Return val + max(left, right) to the parent, since a parent can only extend one branch. Initialize the global maximum to negative infinity so all-negative trees work.
Time O(n) · Space O(h)