A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can only appear in the sequence at most once. The path does not need to pass through the root.

The path sum is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum.

Example 1:

Input:  1 2 3
Output: 6
Explanation: 2 → 1 → 3

Example 2:

Input:  -10 9 20 null null 15 7
Output: 42
Explanation: 15 → 20 → 7

Constraints:

• The number of nodes is in the range [1, 3 × 10⁴]
• -1000 ≤ Node.val ≤ 1000

Input format: BFS level-order, space-separated, null for missing nodes.

Output format: Maximum path sum.