DSA · Trees · #44
Binary Tree Maximum Path Sum
Module 44 · difficulty 4/5·⏱ 30:00starts on first keystroke
A **path** in a binary tree is a sequence of nodes where each adjacent pair is connected by an edge. A node appears at most once on a path, and the path need not pass through the root. The **path sum** is the sum of the node values along the path. Given the `root` of a binary tree, implement `maxPathSum(root)` returning the maximum path sum of any non-empty path. Each node is `{ val, left, right }` (with `left`/`right` being `null` when absent). Values may be negative.
Examples
root = [1,2,3]→6— Optimal path 2 -> 1 -> 3 sums to 6.root = [-10,9,20,null,null,15,7]→42— Optimal path 15 -> 20 -> 7 sums to 42 (the root is excluded).root = [-3]→-3— A single node is a valid path; the best we can do is the node itself.
Constraints
- · The number of nodes is in the range [1, 3 * 10^4].
- · -1000 <= Node.val <= 1000
- · The path must contain at least one node.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.