53. Binary Tree Maximum Path Sum

Hard · Binary Tree

Given a binary tree, find the maximum path sum. 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 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 all node values along the path. You must find the path with the maximum possible sum and return that sum.

Note: The tree is encoded as a level-order (BFS) array with `null` representing missing nodes. For example, `[1, 2, 3]` represents a tree with root 1, left child 2, and right child 3.

Examples

Example 1
Input: [1, 2, 3]
Output: 6
Explanation: The optimal path is 2 → 1 → 3 with sum 2 + 1 + 3 = 6.
Example 2
Input: [-10, 9, 20, null, null, 15, 7]
Output: 42
Explanation: The optimal path is 15 → 20 → 7 with sum 15 + 20 + 7 = 42.

Constraints