Asked at
Binary Tree Maximum Path Sum
HardVerifiedTreeDFSDynamic Programming~32 min
Given the root of a binary tree, return the maximum path sum. A path is any sequence of nodes connected by edges; it need not pass through the root, and contains each node at most once.
Every tree has at least one node, so the answer always exists. A node is { val, left, right } with null children. The input arrives as the root node directly.
Examples
in{val:1, left:{val:2}, right:{val:3}}
out6
Path 2 → 1 → 3 sums to 6.
in{val:-10, left:{val:9}, right:{val:20, left:{val:15}, right:{val:7}}}
out42
Path 15 → 20 → 7 sums to 42; skipping the negative root.
Constraints
- 1 ≤ number of nodes ≤ 3·10⁴
- -1000 ≤ node.val ≤ 1000
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.