Binary Tree Maximum Path Sum

Given a non-empty binary tree, return the maximum path sum. A path may start and end at any two nodes, but it must move only along parent-child connections, and it cannot reuse a node. The path does not need to pass through the root.

Input / output

• Input: root: TreeNode represented by a level-order array with null placeholders
• Output: integer maximum path sum

Examples

1. root = [1,2,3] returns 6 for the path 2 -> 1 -> 3.
2. root = [-10,9,20,null,null,15,7] returns 42 for the path 15 -> 20 -> 7.
3. root = [2,-1] returns 2 because taking the root alone is best.

Constraints

• The number of nodes is in the range [1, 3 * 10^4]
• -1000 <= node.val <= 1000

Target complexity

• Aim for O(n) time with one depth-first traversal and O(h) call-stack space.

Hints

1. For each node, distinguish between the best path you can extend upward to its parent and the best complete path that bends through this node.
2. Negative child contributions should usually be dropped instead of extended.

Follow-up How would you modify the DFS if the interviewer asked for the actual node values on one maximum-sum path, not just the sum?