Best Path Sum in a Tree
A path in a binary tree is a sequence of nodes where each pair of neighbours in the sequence is joined by an edge, and no node appears twice. A path does not have to pass through the root, and it can be a single node.
You are given the root of a non-empty binary tree. Return the largest sum of the values along any path.
Trees in the examples are written level by level, left to right, with null where a child is missing: [1,null,2] is a root 1 with only a right child, 2. [] is an empty tree, with no root at all.
Constraints
- 1 ≤ number of nodes ≤ 10,000
- -1,000 ≤ node value ≤ 1,000
- The tree is at most 1,000 levels deep.
Example 1
The path 2 → 1 → 3 adds up to 6.
Example 2
15 → 20 → 7 adds up to 42. Going through the root would add -10.
Example 3
A path has at least one node, even when every value is negative.
Hints
Was this a good challenge?
- Solved by
- 0
- Submissions
- 0
- Accepted
- –