LeetCode 124 Binary Tree Maximum Path Sum - Why Naive Fails

Try every possible pair of nodes and find the path between them. Calculate path sums.

With $n$ nodes, there are $O(n^2)$ pairs. Finding the path between each pair takes $O(n)$. Total: $O(n^3)$.

Can you compute the maximum path sum in a single traversal?