Maximum Sum of a Continuous Path in a Binary Tree

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

A path is a sequence of nodes where each pair of adjacent nodes in the sequence is connected by an edge, and a node can appear in the sequence at most once. The path does not need to pass through the root, and does not need to start or end at a leaf — it can "bend" at any node (going up into one child and back down into the other), or it can simply be a single node by itself.

Example 1

Input: [1, 2, 3]

      1
     / \
    2   3

Output: 6 — the path 2 -> 1 -> 3 sums to 6.

Example 2

Input: [-10, 9, 20, null, null, 15, 7]

        -10
        /  \
       9    20
           /  \
          15    7

Output: 42 — the path 15 -> 20 -> 7 sums to 42; note that the root -10 is not part of the best path.

Example 3

Input: [-3] → Output: -3 — with all-negative values, the best "path" is the single least-negative node, since a path must be non-empty.

Constraints

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