Binary Tree Maximum Path Sum – Solution & Complexity

• A parent can only continue through at most one child branch, because a path cannot fork upward.
• But the global best path at a node may use both left and right gains together with the node value itself.

• A naive attempt considers many start/end pairs or recomputes subtree sums repeatedly.
• That quickly becomes quadratic on large trees.

• Let the DFS return the best gain a parent can extend through the current node. That gain is node.val + max(leftGain, rightGain, 0).
• At the same time, evaluate the best complete path bending through the node: node.val + max(leftGain, 0) + max(rightGain, 0).
• Update a global maximum with that bending path at every node.

Each node is visited once. The only subtlety is keeping the best path sum local to the current invocation so repeated judge tests do not leak state across runs.

• Returning both child gains upward, which creates an invalid forked path.
• Forcing negative child gains into the path instead of dropping them with max(..., 0).
• Follow-up: to recover the actual path, store which child contributed the extendable gain and which node produced the global best bend.