Binary Tree Maximum Path Sum

Hard

A path is any sequence of nodes connected by parent-child edges; it need not pass through the root. The path sum is the sum of the node values. Given the root, return the maximum path sum of any non-empty path.

Example 1

Input:  root = [1,2,3]
Output: 6

Example 2

Input:  root = [-10,9,20,null,null,15,7]
Output: 42

Constraints

• 1 <= number of nodes <= 3*10^4
• -1000 <= Node.val <= 1000