The problem
A path in a binary tree is a chain of nodes, each linked to the next, with no node used twice; it need not pass through the root and has at least one node. Its sum is the total of its values.
Given the root, return the largest sum of any path. Values can be negative.
Examples
- Input
root = [1, 2, 3]
- Output
6
- Input
root = [-10, 9, 20, null, null, 15, 7]
- Output
42
Constraints
- 1 ≤ number of nodes ≤ 3 × 10⁴
- −1000 ≤ Node.val ≤ 1000
The idea
As in Diameter, every path bends at its highest node: down some way on the left, the node, down some way on the right. For each node, what matters is the best “gain” of a path going straight down from it.
Compute gains bottom-up: a node’s gain is its value plus the larger of its children’s gains, where a negative gain is replaced by 0 — it is better to stop than to add a loss. At each node, value + left gain + right gain is the best path bending there; keep the largest.
- Time
- O(n)
- Space
- O(h)
Solution · every language run against every case
class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: best = root.val def gain(node): # the best sum of a path going down from node (0: take nothing) nonlocal best if not node: return 0 left = max(gain(node.left), 0) # a negative branch is left off right = max(gain(node.right), 0) best = max(best, node.val + left + right) # the best path that bends at node return node.val + max(left, right) gain(root) return best