124. Binary Tree Maximum Path Sum
Your function receives root, the root node of a binary tree in which every node holds an integer val (possibly negative) plus left/right child pointers.
A path is any chain of one or more nodes in which consecutive nodes are joined by a parent–child edge and no node appears twice. A path does not have to pass through the root, start at a leaf, or end at one — but it cannot branch: it goes down one side, optionally through a "peak" node, and down the other.
Return the largest possible sum of node values along any path in the tree. Because a path must contain at least one node, the answer can be negative when every value is negative.
Example 1:
Input: root = [1, 2, 3]
Output: 6
Explanation: The path 2 → 1 → 3 uses every node: 2 + 1 + 3 = 6. Any shorter path sums to less.
Example 2:
Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42
Explanation: The best path is 15 → 20 → 7 with sum 42. Extending it up through the -10 root would subtract 10, so the path stays inside the right subtree.
Constraints:
- 1 ≤ number of nodes ≤ 3 * 10⁴
- -1000 ≤ node.val ≤ 1000
Hints:
Every path has a unique highest node — its "peak". Seen from the peak, a path is a downward chain into the left subtree plus a downward chain into the right subtree (either side may be empty).
So for each node you want the best *downward-only* chain starting at each child. If a chain's sum is negative, using nothing (0) is better than attaching it.
One post-order DFS can do both jobs at once: return the best downward chain from each node to its parent, while updating a global best with val + leftChain + rightChain at every node.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3]
Expected output: 6