Binary Tree Maximum Path Sum

Given the root of a binary tree, return the maximum path sum of any non-empty path.

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can appear in the path at most once. The path does not need to pass through the root, and it must contain at least one node.

Node values can be negative.

---

Example 1

    1
   / \
  2   3

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 → 1 → 3 with a sum of 2 + 1 + 3 = 6.

Example 2

       -10
       /  \
      9   20
         /  \
        15   7

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 → 20 → 7 with a sum of 15 + 20 + 7 = 42.

---

Constraints

• The number of nodes in the tree is in the range [1, 3 * 10^4].
• -1000 <= Node.val <= 1000