861. Binary Tree Maximum Path Sum
Hard•
Given the root of a nonempty binary tree, return the largest sum of values on a nonempty path.
A path follows parent-child edges and may start and end at any nodes. It does not have to pass through the root. No node may be visited twice.
Example inputs use level-order arrays with null for a missing child. Your function receives a TreeNode object with val, left, and right fields.
Example 1:
Input: root = [5,2,8]
Output: 15
Explanation: The path 2 -> 5 -> 8 has sum 15.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The path 15 -> 20 -> 7 has sum 42 and does not include the root.
Example 3:
Input: root = [-3]
Output: -3
Explanation: The path must contain a node, so the answer cannot be zero.
Constraints
- 1 <= number of nodes <= 30000
- -1000 <= node.val <= 1000
Accepted2/3|Acceptance Rate66.7%