Binary Tree — Maximum Path Sum

A path is any sequence of nodes connected by edges, going up and/or down, that
visits each node at most once. It does not have to pass through the root or end at
a leaf. Its sum is the sum of its node values.

solve(levelOrder) receives a non-empty tree serialized level by level (values
may be negative) and returns the maximum path sum.

Examples

solve([1, 2, 3])                                         → 6     // 2 → 1 → 3
solve([-10, 9, 20, null, null, 15, 7])                   → 42    // 15 → 20 → 7
solve([-3])                                              → -3    // a path needs at least one node
solve([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]) → 48

This extends the diameter problem: each recursive call returns the best sum of a
path that goes down from the node, while a separate variable tracks the best
path that bends at the node.