LeetCode 124 · Trees · concept: dfs-pattern
Problem
A path is any sequence of connected nodes (need not pass through the root). Return the maximum sum of node values along any path.
-10
9 20 -> 42 (15 -> 20 -> 7)
15 7
Approach — DFS returning the best “downward arm” + global max (optimal)
Two different quantities per node, and mixing them up is the classic mistake:
- Returned upward: the best path that goes down one side only —
node.val + max(leftArm, rightArm, 0). A parent can only extend through one child. - Used to update the global answer: the best path with this node as the peak —
node.val + leftArm + rightArm(both arms joined here). This path can’t extend to a parent, so it’s only for the answer, never returned.
def maxPathSum(root):
best = float("-inf")
def dfs(node):
nonlocal best
if not node:
return 0
left = max(dfs(node.left), 0) # drop negative arms
right = max(dfs(node.right), 0)
best = max(best, node.val + left + right) # path peaking here
return node.val + max(left, right) # extendable arm for the parent
dfs(root)
return bestTime O(n), space O(h).
The two crucial subtleties
- Clamp negative arms to 0 — a subtree that only subtracts should be dropped, not included.
- Return one arm, but score with both — a path through a node uses both children (the “peak”), yet a node handed up to its parent can only contribute one side (else it wouldn’t be a simple path). Conflating these two is the bug that makes this problem hard.
Key insight
Distinguish “answer at this node” (both arms) from “value returned to the parent” (one arm). It’s the most refined form of the dual-purpose DFS from Diameter — Diameter counts edges, this sums values, but the shape is identical.
Related
- concept: dfs-pattern
- relative: Diameter of Binary Tree
- prev: Construct Tree · next: Serialize and Deserialize Binary Tree
Jump to a subject
Software engineering
Infrastructure & security
Computer science
Hardware & engineering