Path Sum IV
Problem
Each entry is a 3-digit number: depth, position-in-row, value. Sum all root-to-leaf path sums.
nums = [113,215,221]12def path_sum(nums):
tree = {(n // 100, (n % 100) // 10): n % 10 for n in nums}
def dfs(d, p, s):
if (d, p) not in tree: return 0
s += tree[(d, p)]
l, r = (d + 1, 2 * p - 1), (d + 1, 2 * p)
if l not in tree and r not in tree: return s
return dfs(*l, s) + dfs(*r, s)
return dfs(1, 1, 0)function pathSum(nums) {
const t = new Map();
for (const n of nums) t.set((Math.floor(n / 100)) * 100 + Math.floor((n % 100) / 10), n % 10);
const dfs = (d, p, s) => {
const k = d * 100 + p;
if (!t.has(k)) return 0;
s += t.get(k);
const lk = (d + 1) * 100 + 2 * p - 1, rk = (d + 1) * 100 + 2 * p;
if (!t.has(lk) && !t.has(rk)) return s;
return dfs(d + 1, 2 * p - 1, s) + dfs(d + 1, 2 * p, s);
};
return dfs(1, 1, 0);
}int pathSum(int[] nums) {
Map t = new HashMap<>();
for (int n : nums) t.put((n / 100) * 100 + (n % 100) / 10, n % 10);
return dfs(1, 1, 0, t);
}
int dfs(int d, int p, int s, Map t) {
int k = d * 100 + p;
if (!t.containsKey(k)) return 0;
s += t.get(k);
int lk = (d + 1) * 100 + 2 * p - 1, rk = (d + 1) * 100 + 2 * p;
if (!t.containsKey(lk) && !t.containsKey(rk)) return s;
return dfs(d + 1, 2 * p - 1, s, t) + dfs(d + 1, 2 * p, s, t);
} unordered_map t;
int dfs(int d, int p, int s) {
int k = d * 100 + p;
if (!t.count(k)) return 0;
s += t[k];
int lk = (d + 1) * 100 + 2 * p - 1, rk = (d + 1) * 100 + 2 * p;
if (!t.count(lk) && !t.count(rk)) return s;
return dfs(d + 1, 2 * p - 1, s) + dfs(d + 1, 2 * p, s);
}
int pathSum(vector& nums) {
for (int n : nums) t[(n / 100) * 100 + (n % 100) / 10] = n % 10;
return dfs(1, 1, 0);
} Explanation
The tree here is given as a list of 3-digit codes where the digits are depth, position-in-row, and value. The first step is to decode these into a lookup table keyed by (depth, position) so we can find any node instantly.
The decoding splits each number: n // 100 is the depth, (n % 100) // 10 is the position, and n % 10 is the value. We store value under key (depth, position) in the map tree.
The handy property of this numbering is that a node at position p has children at positions 2*p - 1 and 2*p one level down. So during DFS we can compute child keys directly instead of storing pointers.
We DFS from (1, 1) carrying the running path sum s. When a node has no children present in the map it is a leaf, and we return the accumulated s; otherwise we return the sum from the left plus the sum from the right.
Example: [113,215,221] decodes to root 3 with children 5 and 1. The two leaf paths sum to 3+5=8 and 3+1=4, so the total is 12.