Tree DFS
LC #124Hard
Binary Tree Maximum Path Sum
Tree DFS
AmazonGoogleMetaBloombergProblem
Find the maximum path sum where the path can start and end at any node.
treedfsdynamic-programming
Constraints
- ›1 ≤ n ≤ 3 × 10⁴
- ›-1000 ≤ Node.val ≤ 1000
- ›Path can start and end at any node; must contain at least one node
Example
Input
root = [-10, 9, 20, null, null, 15, 7]Output
42Why
Optimal path: 15 → 20 → 7 = 42 (does not have to pass through root)