119. Binary Tree Maximum Path Sum
HardTrees
A path is a sequence of nodes where each adjacent pair is joined by an edge, and no node appears twice. The path does not need to pass through the root. Return the largest sum of node values over all non-empty paths.
A binary tree is passed as TreeNode objects with val, left and right. The tests write trees in level order, with null for a missing child.
Example 1
Input: root = [-10, 9, 20, null, null, 15, 7] Output: 42 Explanation: The path 15 → 20 → 7.
Constraints
1 ≤ nodes ≤ 3 · 10⁴-1000 ≤ value ≤ 1000