Loading problem…
A path in a binary tree is a sequence of nodes. Return the maximum path sum of any non-empty path. Tree is given as level-order array with null for missing nodes.
Example 1
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The best path is 15 → 20 → 7, with sum 15 + 20 + 7 = 42. Extending it up to -10 or over to 9 would only lower the total.
Example 2
Input: root = [1,2,3]
Output: 6
Explanation: The path 2 → 1 → 3 uses every node and has sum 2 + 1 + 3 = 6.
Example 3
Input: root = [-3]
Output: -3
Explanation: A path must contain at least one node, and the only node is -3, so the maximum path sum is -3.
At any node, the best path that **passes through** it is `node.val + max(0, left_gain) + max(0, right_gain)`. But when returning upward, we can only carry a **single branch** (left or right), because the parent needs a linear chain to extend.
Run checks all cases above. Submit evaluates all test cases.