A road map is a binary tree whose edges can be driven in both directions. Each town has a value node.val: non-negative values are scenic points, negative values are tolls. A route is a path that visits one or more distinct towns, each consecutive pair joined by an edge; its score is the sum of the values of its towns.
Return the highest score of a route that passes through at most one town with a negative value. Zero is not negative. Return 0 for an empty tree.
Examples
4
/ \
-2 -3
/ \ / \
6 1 5 -10
Input: root = build_tree([4, -2, -3, 6, 1, 5, -10])
Output: 8
Explanation: 6 -> -2 -> 4 scores 8. The route 6 -> -2 -> 4 -> -3 -> 5 would score 10
but pays two tolls.
Input: root = build_tree([-5, -1])
Output: -1
Explanation: both towns together would be two tolls, so the best route is the single town -1.
Input: root = build_tree([3, 3, -1, None, None, 3, 3])
Output: 8
Constraints
0 <= number of nodes <= 10**5-1000 <= node.val <= 1000- The tree may be a single chain, so its height can equal the number of nodes.
Goals
- Carry two downward results per node: with no negative node, and with at most one
- Join a left chain and a right chain at their top node without exceeding the limit
- Process children before parents with an explicit order instead of recursion