Binary Tree Maximum Path Sum
In a binary tree, a path is a sequence of nodes where each consecutive pair is connected by an edge and no node repeats. A path can start and end anywhere — it does not need to touch the root or reach a leaf — but it must contain at least one node. Given the root, return the largest possible sum of node values along any path.
The tree has 1 to 30,000 nodes and values range from -1000 to 1000 — negatives are the whole difficulty, since sometimes the best path excludes a subtree entirely.
Examples
- Input:
- root = [1,2,3]
- Output:
- 6
The path 2 → 1 → 3 uses all three nodes: 2 + 1 + 3 = 6.
- Input:
- root = [-10,9,20,null,null,15,7]
- Output:
- 42
The best path is 15 → 20 → 7 = 42, living entirely inside the right subtree and skipping the -10 root.
- Input:
- root = [-3]
- Output:
- -3
A path must contain at least one node, so with all values negative the answer is the least-bad single node.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.