Binary Tree Maximum Path Sum

Problem

A path in a binary tree is a sequence of nodes in which each consecutive pair is connected by an edge and no node appears twice. A path can start and end at any nodes and does not have to pass through the root, but it must contain at least one node. The sum of a path is the sum of its nodes' values. Given the root, return the maximum path sum over all paths in the tree.

• The tree has between 1 and 60,000 nodes.
• Node values are integers between -5,000 and 5,000; an all-negative tree is a valid input.

Examples

• root = [4, 7, 2] → 13. The path 7 → 4 → 2 uses all three nodes.
• root = [-8, 6, 15, None, None, 11, 9] → 35. The path 11 → 15 → 9 avoids the negative root entirely.
• root = [-6] → -6. The path must contain at least one node, so an all-negative tree still has an answer.
• root = [3, -2] → 3. Including the -2 would only lower the sum.

Hints

1. Every path has a unique topmost node where it bends. Describe the best path through a given node in terms of its two subtrees.
2. A subtree can contribute to a path that continues upward only through a single downward branch, and it should contribute nothing at all if its best branch is negative.
3. Post-order DFS returning the best single-branch gain, max(0, node.val + max(gain_left, gain_right)), while recording node.val + gain_left + gain_right as a candidate answer.