LeetCode 124 Binary Tree Maximum Path Sum - Example and Complexity Analysis

Trace -10(9, 20(15, 7)).

Process 15 (leaf): gain = 15. Max path through 15 = 15. Global max = 15.

Process 7 (leaf): gain = 7. Max path through 7 = 7. Global max = 15.

Process 20: leftGain = 15, rightGain = 7.

• Path through 20: 15 + 20 + 7 = 42. Global max = 42.
• Gain to parent: 20 + max(15, 7) = 35.

Process 9 (leaf): gain = 9. Max path = 9. Global max = 42.

Process -10: leftGain = 9, rightGain = 35.

• Path through -10: 9 + (-10) + 35 = 34. Global max still 42.
• Gain to parent: -10 + 35 = 25.

Return 42.

Visit each node once. $O(n)$ time. Recursion stack: $O(h)$ space.