Description
Given the root of a binary tree, return the maximum path sum of any non-empty path. A path can start and end at any node in the tree.
Examples
Input:
root = [1,2,3]Output:
6Explanation:
Path 2 → 1 → 3 has sum 6.
Input:
root = [-10,9,20,null,null,15,7]Output:
42Explanation:
Works with negative numbers.
Input:
root = [5,-3,8,2,4,null,6,null,null,-1,null,null,7]Output:
19Explanation:
The optimal path is 7->6->8->5->4 with sum 7+6+8+5+4=30. Negative nodes are excluded from the path since they would reduce the total.
Constraints
- •
Number of nodes is in range [1, 3 × 10⁴] - •
-1000 ≤ Node.val ≤ 1000