Binary Tree Maximum Path Sum
Recognize the pattern
Brute force idea
If you approach Binary Tree Maximum Path Sum in the most literal way possible, you get this: Check every possible path. For each node, compute the best path through it independently. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
Better approach
The real unlock in Binary Tree Maximum Path Sum comes when you notice this: DFS returning max single-path sum. At each node, compute the through-path (left + node + right) and update global max. Return the best one-sided path (node + max(left, right)) for the parent to use. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Key invariant
The compass for Binary Tree Maximum Path Sum is this: At each node, the maximum path THROUGH it is left_gain + node.val + right_gain (where gains are clamped to 0). But the value returned to the parent is node.val + max(left_gain, right_gain) — you can only extend in one direction upward. As long as that statement keeps holding, you can trust the steps built on top of it.
Watch out for
The trap in Binary Tree Maximum Path Sum usually looks like this: Returning the through-path value to the parent — a path can't fork. You must return the best single-sided path. The through-path is only used to update the global maximum. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.