A path in a binary tree is a sequence of nodes where each pair of neighbours is joined by an edge. A node appears at most once in a path, and the path doesn't have to pass through the root.
Given the root of a binary tree, return the largest sum of node values over any non-empty path.
Examples
Example 1
- Input
- root = [1, 2, 3]
- Output
- 6
- Why
- The path 2 → 1 → 3 adds up to 6.
Example 2
- Input
- root = [-10, 9, 20, null, null, 15, 7]
- Output
- 42
- Why
- The path 15 → 20 → 7 adds up to 42.
Constraints
- The tree has between
1and3 * 10^4nodes. -1000 <= Node.val <= 1000