LeetCode 124 Binary Tree Maximum Path Sum - Implementation

Negative nodes complicate things. We might want to exclude a subtree entirely if its contribution is negative. Trick: when computing $maxDown$, take $\max(0, childMaxDown)$. This lets us "cut off" negative subtrees. Base case: null node returns $maxDown = 0$, $maxPath = -\infty$. Leaf returns $(val, val)$. Time: $O(n)$ single post-order traversal. Space: $O(h)$ for recursion stack where $h$ is tree height.

Time complexity: $O(n)$.

Space complexity: $O(h)$.