A trail map is a binary tree whose edges can be walked in both directions. Every junction has a score node.val, which may be negative. A hike from junction s is a path that starts at s and never visits a junction twice; it may stop anywhere, even at s itself. Its score is the sum of the values of all junctions on it, including s.
For every junction, find the best score of a hike that starts there. Return these scores in level order (top to bottom, left to right within a level). Return [] for an empty tree.
Examples
2
/ \
-5 4
/ / \
3 -1 6
Input: root = build_tree([2, -5, 4, 3, None, -1, 6])
Output: [12, 7, 10, 10, 9, 12]
Explanation: from the leaf 3 the best hike is 3 -> -5 -> 2 -> 4 -> 6 with score 10;
from -1 it is -1 -> 4 -> 6 with score 9.
Input: root = build_tree([-3, -7])
Output: [-3, -7]
Explanation: every longer hike only loses points, so each junction stops at once.
Constraints
0 <= number of nodes <= 6 * 10**4-1000 <= node.val <= 1000- The tree may be a single chain, so its height can equal the number of nodes.
Goals
- Split a path from a node into a downward part and an upward part
- Pass the best 'upward' score from a parent to each child, excluding the child's own branch
- Answer a question for every node in linear time on deep trees