LeetCode 124 Binary Tree Maximum Path Sum - Walkthrough

Tree: root $-10$, left $9$, right $20$ (left $15$, right $7$). DFS leaf $15$: returns $15$. DFS leaf $7$: returns $7$. DFS node $20$: leftMax $= 15$, rightMax $= 7$. Updates maxPath $= 20 + 15 + 7 = 42$.

Returns $20 + 15 = 35$. DFS leaf $9$: returns $9$. DFS root $-10$: leftMax $= 9$, rightMax $= 35$. Updates maxPath $= \max(42, -10 + 9 + 35) = \max(42, 34) = 42$. Returns $-10 + 35 = 25$. Answer: $42$.