A downward path starts at any node of a binary tree and moves only from a node to one of its children, stopping at any node (a single node is a downward path). Given the root and a positive integer k, return the number of nodes on the longest downward path whose values add up to a multiple of k. Return 0 if no such path exists (including for an empty tree). Values may be negative, and 0 counts as a multiple of k.
Examples
4
/ \
3 1
/ \ \
2 5 6
Input: root = build_tree([4, 3, 1, 2, 5, None, 6]), k = 3
Output: 3
Explanation: 4 -> 3 -> 2 adds up to 9 (and 4 -> 3 -> 5 to 12).
Input: root = build_tree([4, 3, 1, 2, 5, None, 6]), k = 7
Output: 2
Explanation: 4 -> 3 and 1 -> 6 both add up to 7; no longer path works.
Input: root = build_tree([1, 1]), k = 5
Output: 0
Constraints
0 <= number of nodes <= 10**5-10**4 <= node.val <= 10**41 <= k <= 10**9- The tree may be a single chain, so its height can equal the number of nodes.
Goals
- Keep prefix sums of the current root path in a dictionary while walking the tree
- Store the shallowest depth for each remainder and undo it when leaving that node
- Handle negative values with remainders