Solution:

The trick is to notice that a path is allowed branch into 2 parts at the very top, but the path cannot branch as it goes lower down.

This means that the max path through a node contains the node's value. It also either contains a path that goes strictly down through the left node, or through the right node, or it contains both these paths, or neither. Here are all of the possible paths one can take through a node:

Both:

Left:

Right:

Neither:

Here's an equation for this:

When we write maxPathDown, we mean a path strictly downwards, which never splits in two.

1. Recursion

The above equation isn't recursive, so it feels like we're stuck. But it's clear how to compute maxPathDown recursively. The max path downwards, starting at a node, always contains the node's value, and it either contains the path to the left, or the path to the right, or neither. It just can't contain both, because that would make it split in two. Here's the recursion for maxPathDown:

This recursion already computes everything we need in order to compute maxPath. So a clever idea is to "hijack" the recursion to also compute the max path going through this node. We can do this by just sticking in a line of code:

2. Base case

Eventually the recursion gets to a node that's null. The maximum path through a null node is 0.

3. Code

Combining the recursion and base case, and keeping track of the largest maxPath we see, we get this code:

Time Complexity $O(n)$. We visit every node once.

Space Complexity $O(n)$. The recursion might get n nodes deep, so the Call Stack grows to size O(n).