Compute maximum path sum in a binary tree

You are given the root of a binary tree where each node contains an integer value (which may be positive, zero, or negative).

A path in the tree is defined as any sequence of nodes such that:

• Each pair of consecutive nodes in the sequence is connected by an edge in the tree.
• A path may start and end at any nodes in the tree.
• A path must contain at least one node.
• The path cannot reuse the same node more than once (i.e., it is a simple path; it does not branch or form cycles).

The path sum is the sum of the node values along that path.

Task

Implement a function that returns the maximum path sum over all possible paths in the tree.

Function Signature

You can assume a typical binary tree node definition, for example in a C++/Java-like style:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

Write a function:

int maxPathSum(TreeNode root)

which returns the maximum path sum.

Constraints

• The number of nodes in the tree is in the range [1, 3 * 10^4].
• Each node value is in the range [-10^3, 10^3].
• The tree is not necessarily balanced.

Examples

Example 1

Input tree (level-order representation): [1, 2, 3]

This corresponds to the structure:

    1
   / \
  2   3

All possible simple paths and their sums:

• 2 → 1 → 3 has sum 2 + 1 + 3 = 6
• 2 → 1 has sum 3
• 1 → 3 has sum 4
• Single-node paths: 2, 1, 3

Output: 6

Example 2

Input tree (level-order): [-10, 9, 20, null, null, 15, 7]

Structure:

     -10
     /  \
    9    20
        /  \
       15   7

The maximum path is 15 → 20 → 7 with sum 15 + 20 + 7 = 42.

Output: 42

Example 3

Input tree (single node): [-3]

Only one possible path: the single node itself.

Output: -3

Notes

• The maximum path is allowed to start and end at any two nodes in the tree.
• The path is not required to pass through the root.