Binary Tree Maximum Path Sum

Problem: Binary Tree Maximum Path Sum Given the root of a non-empty binary tree, where every node contains an integer, return the maximum sum of values along any non-empty path. A path is a sequence of nodes connected by parent-child edges. It may start and end at any nodes, does not need to pass through the root, and cannot contain a node more than once. Example 1 Input: root = [1,2,3] Output: 6 Explanation: The path 2 -> 1 -> 3 has sum 6. Example 2 Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The path 15 -> 20 -> 7 has sum 42. Constraints 1 <= n <= 3 * 10^4 -1000 <= Node.val <= 1000 The input is represented as a level-order array, where null denotes a missing node. Example Input [1,2,3] Output 6