Max Path Sum

We need to find a path that maximizes the sum of node values. A path can go up from a left child to the root and then down to the right child. For any node, the max path passing through it (as the highest point) is node.val + max_gain_from_left + max_gain_from_right.

Tree DP (Post-order Traversal):

We solve this using recursion. For each node, we want two things:

• To Parent: The max path sum starting at this node and going down (to be used by its parent). This is node.val + max(left_gain, right_gain).
• Global Max: The max path sum that pivots at this node. This is node.val + left_gain + right_gain. We update a global variable with this value.

Note: If a gain is negative, we ignore it (take 0 instead).

Algorithm:

1. Initialize globalMax to negative infinity.
2. Perform a post-order traversal (Left, Right, Root).
3. For node:
• Recursively get leftGain = max(0, dfs(node.left)).
• Recursively get rightGain = max(0, dfs(node.right)).
• Update globalMax = max(globalMax, node.val + leftGain + rightGain).
• Return node.val + max(leftGain, rightGain) to the parent.

Visualizing the Tree:

• Bottom-Up: Leaf nodes return their value (if positive).
• Combination: Internal nodes combine gains from children.
• Bridge: The "bridge" formed by left -> root -> right is potentially the max path.

"Binary tree", "Maximum path sum", "Any node to any node".