Best Trail Payout

hard

A treasure park is laid out as a binary tree; every station holds a payout — sometimes negative (a toll). You may start your walk at any station and stop at any station, moving only along edges and never revisiting a station. Your route is one continuous path through the tree: it may bend through a station from one child to the other, but it cannot branch.

Given the root, return the maximum possible sum of station values along any such path. The path must contain at least one station, so with all tolls the answer is the least-bad single station.

Tests pass a level-order array; implement the core in _max_path on real nodes.

Example 1

in values = [1, 2, 3]

out 6

Take all three: 2 → 1 → 3.

Example 2

in values = [-10, 9, 20, null, null, 15, 7]

out 42

Best route is 15 → 20 → 7; the -10 root is dead weight, so skip it.

Example 3

in values = [2, -1]

out 2

Extending to the -1 only hurts — stop at the root.

Constraints

· 1 <= number of nodes <= 3 * 10^4
· -1000 <= node value <= 1000
· the path must contain at least one node