• The number of nodes in the tree is in the range [1, 3 × 10⁴]
• -1000 <= Node.val <= 1000
• The path must be non-empty — the empty path is not a valid answer
• The path need not include the root or any leaf

A path is any connected route through the tree with no node repeated, and we want the one whose values add up to the most. It can start and stop anywhere — no need to touch the root. The twist that makes it interesting: values can be negative, so a longer path isn't always richer. Sometimes you stop.

Here the best path is 15 – 20 – 7, totalling 42. Notice it bends at 20 and never reaches the root:

       -10
       /  \
      9    20        best path: 15 + 20 + 7 = 42
          /  \
        15    7

Stand on a node after its children have reported their best downward runs. You now care about two things — and confusing them is the whole bug. Look at node 20:

        20
       /  \
     15    7

  (A) path that BENDS at 20:   15 + 20 + 7   = 42   <- uses BOTH arms, finished
  (B) run 20 offers UPWARD:    20 + max(15,7) = 35   <- uses ONE arm, can extend

(A) is a finished path: it already spent both of 20's arms, so it can't climb any higher — it just competes for the best-so-far. (B) is what 20 hands to its parent: a path continuing up through 20 can only enter one arm, or it forks and stops being a path. So the rule is simple: record (A) on the side, return (B) upward.

An arm can come back negative. You're never forced to walk into it, so clamp each arm at 0 — take it only if it helps:

        2
       / \
     -1   -2      both arms negative -> drop both -> best path is just 2

best = float('-inf')

def gain(node):
    nonlocal best
    if node is None:
        return 0
    left  = max(0, gain(node.left))            # take the arm only if it helps
    right = max(0, gain(node.right))
    best = max(best, node.val + left + right)   # (A) path bends here
    return node.val + max(left, right)          # (B) run offered upward

gain(root)
return best

Two traps the pictures hide:
- node.val itself is never clamped — only its arms are. On an all-negative tree like a lone -3, both arms clamp to 0 and the best is -3 + 0 + 0 = -3. Start best at negative infinity, not 0, or you'd claim the empty path (sum 0), which isn't allowed.
- (A) adds both arms, (B) keeps the better one — same reason as the picture: a path bending here uses both directions at once; a path continuing upward may leave on only one.

Tree above, root -10:
- Leaf 15 → arms 0, 0 → candidate 15 (best = 15); offers up 15.
- Leaf 7 → candidate 7; offers up 7.
- Node 20 → arms 15 and 7 → candidate 20 + 15 + 7 = 42 (new best!); offers up 20 + max(15, 7) = 35.
- Leaf 9 → candidate 9; offers up 9.
- Root -10 → arms max(0,9) = 9 and max(0,35) = 35 → candidate -10 + 9 + 35 = 34 (loses to 42); offers up -10 + 35 = 25 (nobody reads it).
- Answer 42 — recorded three steps earlier, deep in the tree.

Because every node drops its own (A) candidate into best, the winning path can live anywhere — no special case needed. O(N) time, O(H) stack.