Why it works
- Every path has one highest node, where it bends: it comes up one side and goes down the other. So it is enough to try each node as that bend, with the best branch down on each side.
- A branch with a negative sum only makes a path worse, so max(gain, 0) drops it, and the path simply stops at the node.
- Up to the parent goes one side only: a path through the parent that came down here cannot fork into both branches. The two-sided sum goes into best instead.
Complexity
Time O(n): each node is visited once. Memory O(h), where h is the height of the tree: the call stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗