45 / 75
Hard
Binary Tree Maximum Path Sum
#45treedfsrecursionpost-order
Track global max while DFS returns max single-path sum from each node.
Example:
Input:
root=[-10,9,20,null,null,15,7]Output:
42 (path: 15->20->7)Common Mistakes:
- Returning path through node instead of single path to parent
- Not handling negative values (use Math.max(0, ...) to ignore negative paths)
- Forgetting that path can be just a single node
- Confusing what to return vs what to track in global variable
Notes:
Tricky: return value (max path ending at node) differs from what we track (max path through node). Time O(n), Space O(h).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Track global max while DFS returns max single-path sum from each node.
Example:
Input:
root=[-10,9,20,null,null,15,7]Output:
42 (path: 15->20->7)Common Mistakes:
- Returning path through node instead of single path to parent
- Not handling negative values (use Math.max(0, ...) to ignore negative paths)
- Forgetting that path can be just a single node
- Confusing what to return vs what to track in global variable
Notes:
Tricky: return value (max path ending at node) differs from what we track (max path through node). Time O(n), Space O(h).
45/75
Binary Tree Maximum Path Sum