LeetCode 124 Binary Tree Maximum Path Sum - Algorithm

Run DFS from root. For each node:

$1.$ Compute $ext{leftMax} = max( ext{dfs}( ext{left}), 0)$.

$2.$ Compute $ext{rightMax} = max( ext{dfs}( ext{right}), 0)$.

$3.$ Update $ext{maxPath} = max( ext{maxPath}, v + ext{leftMax} + ext{rightMax})$.

$4.$ Return $v + max( ext{leftMax}, ext{rightMax})$ to parent.

After DFS, return $ext{maxPath}$. The global variable accumulates the best answer seen at any node.

This runs in $O(n)$ time and uses $O(n)$ space.