Binary Tree Maximum Path Sum
HardTrees
Given the root of a non-empty binary tree, return the largest possible *path sum*.
- A *path* is a sequence of nodes where each consecutive pair is joined by a parent-child edge. Each node appears at most once.
- A path contains at least one node. It can start and end anywhere and does not have to pass through the root; it may go up to some node and then back down into that node's other subtree.
- The *path sum* is the sum of the values of the nodes on the path.
Node values can be negative.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [-5,4,10,null,null,6,8]
- Output:
- 24
- Explanation
- The best path is 6 → 10 → 8 with sum 24. Any path that reaches the root picks up its -5: for example 4 → -5 → 10 → 8 only sums to 17.
Example 2
- Input:
- root = [-3,-2,-5]
- Output:
- -2
- Explanation
- Every value is negative, so the best path is the single least negative node, -2. Joining more nodes only makes the sum smaller.
Example 3
- Input:
- root = [2,-1]
- Output:
- 2
- Explanation
- Taking the root alone gives 2. Adding the -1 child would lower the sum to 1, so the child is left out.
Constraints
- The number of nodes is in the range
[1, 3 * 10^4] -1000 <= Node.val <= 1000- The tree height is at most
500