Binary Tree Maximum Path Sum
HardP2Coding
A path in a binary tree is a sequence of nodes where each adjacent pair is connected by an edge and no node appears twice. It does not have to pass through the root or end at a leaf, but it must contain at least one node. The path sum is the sum of its node values.
Given the root of a binary tree, return the maximum path sum over all non-empty paths.
Example 1
- Input
- root = [1,2,3]
- Output
- 6
- Why
- The path 2 -> 1 -> 3.
Example 2
- Input
- root = [-10,9,20,null,null,15,7]
- Output
- 42
- Why
- The path 15 -> 20 -> 7.
Constraints
- 1 <= number of nodes <= 3 * 10^4
- -1000 <= Node.val <= 1000
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.