Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 124 Binary Tree Maximum Path Sum - Solution

The core idea

Think about each node as a potential "turning point" of a path. A path through node X might go: left subtree → X → right subtree.

For each node, compute two things:

  1. The max path sum where this node is the highest point (can include both children).
  2. The max "gain" this subtree can contribute to a path that continues upward (can include at most one child).

Use post-order traversal. After processing children, compute the max path sum with current node as turning point. Update the global maximum. Return the max gain for the parent's calculation.

If a subtree's gain is negative, don't include it (use 0 instead).