Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root. The path sum is the sum of the node values in the path. Find the maximum path sum. Input root: the root of the binary tree Output Return the largest path sum Example 1: Input: root = [1,2,3] Output: 6 Explanation: The path 2->1->3 has the largest path sum which is 6. Example 2: Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The path 15->20->7 has the largest path sum which is 42. Constraints Number of nodes in the tree is in the range [1, 3 * 10^4]. -1000 <= Node.val <= 1000 Example Input 1,2,3