Binary Tree Maximum Path Sum

You are given the root of a binary tree in which every node stores an integer value (values may be negative, zero, or positive).

Define a path as any sequence of nodes where each consecutive pair is connected by a parent-child edge. A path may start and end at any node, must contain at least one node, and cannot branch — each node in the path may connect to at most two neighbors within the path (meaning the path can bend at most once, at a single "peak" node, but cannot revisit a node or use a node more than twice).

Your task is to compute the maximum possible sum of node values along any such path in the tree, and return that sum.

Notes to keep in mind:

• The path does not need to pass through the root.
• A path consisting of a single node is valid, so the answer is never undefined even if all values are negative.
• The tree can contain negative values, so a valid path might choose to skip attaching a child subtree if doing so would lower the sum.

Examples

Example 1:

Input: root = [2,4,-1] (meaning node 2 has left child 4 and right child -1)

Output: 6

Explanation:

• The path 4 -> 2 -> -1 sums to 4 + 2 + (-1) = 5.
• The path consisting of just 4 and 2 (4 -> 2) sums to 6, which is higher because including the -1 child would only reduce the total.
• The maximum among all candidate paths is 6.

Example 2:

Input: root = [-5,8,-3,2,7,null,-2] (meaning -5 is root; its left child is 8 with children 2 and 7; its right child is -3 with right child -2)

Output: 17

Explanation:

• Consider the path 2 -> 8 -> 7, which sums to 2 + 8 + 7 = 17.
• No other path, including ones that route through the root -5, produces a higher sum, since -5 and -3 only decrease any total they're added to.
• Therefore 17 is the maximum achievable path sum.

Constraints

• The tree contains between 1 and 3 * 10^4 nodes.
• Each node's value is an integer between -1000 and 1000.
• The tree is a standard binary tree (not necessarily balanced or complete).