A trail map is a binary tree: every node is a junction and every parent-child edge is a trail of length 1 that can be walked in both directions. node.val is the number of hikers waiting at that junction.
The group will light one campfire at a junction s, and every hiker walks to it. The walking total for s is the sum, over all junctions u, of u.val * dist(u, s), where dist counts edges.
Return a list with the walking total for every junction, listed in level order (top to bottom, and left to right within a level). Return [] for an empty tree.
Examples
1
/ \
2 3
\
4
Input: root = build_tree([1, 2, 3, None, 4])
Output: [13, 11, 17, 13]
Explanation: at the root the walks are 2*1 + 3*1 + 4*2 = 13; at the junction holding 2
they are 1*1 + 3*2 + 4*1 = 11.
Input: root = build_tree([0, 0, 7])
Output: [7, 14, 0]
Input: root = build_tree([5])
Output: [0]
Constraints
0 <= number of nodes <= 6 * 10**40 <= node.val <= 1000- The tree may be a single chain, so its height can equal the number of nodes.
Goals
- Compute one answer for the root, then shift it to each child in O(1)
- Use subtree weight totals to see how a move changes every distance at once
- Process a very deep tree without recursion