Binary Tree Maximum Path Sum

You get the root of a binary tree. Each node holds a whole number, and some may be negative. Return the largest sum of values along any path in the tree.

A path goes from node to node along the edges. It never uses a node twice. It can start and end at any node. It doesn't have to include the root. A single node is a path too.

The trees below are listed level by level, top to bottom and left to right. A missing child is written as NULL.

Example 1:

      4
     / \
   -6   5
   / \
  8   3

Input: root = [4,-6,5,8,3]
Output: 11
Explanation: The best path is 8 → -6 → 4 → 5.
Its sum is 8 - 6 + 4 + 5 = 11.
Going through -6 is worth it to reach the 8.

Example 2:

     -1
     /
    7
   / \
 -2   3
     /
    4

Input: root = [-1,7,NULL,-2,3,NULL,NULL,4]
Output: 14
Explanation: The best path is 4 → 3 → 7.
Its sum is 4 + 3 + 7 = 14.
It stops at 7, because the root would add -1.

Example 3:

    -7
   /  \
 -3    -5

Input: root = [-7,-3,-5]
Output: -3
Explanation: Every value is negative.
Each extra node lowers the sum.
The best path is the single node -3.

Constraints:

• 1 to 30,000 nodes.
• Each value is from -1,000 to 1,000.
• The tree is at most 400 levels deep.