Path Sum IV

Problem

Tree nodes are encoded as 3-digit integers: hundreds = depth (1-based), tens = position (1-based), units = value. Return sum of all root-to-leaf paths.

Key insight: Build map: (depth, pos) → value. DFS using parent's position to find children.

Solutions

// C++
int pathSum(vector<int>& nums) {
    unordered_map<int, int> mp;
    for (int n : nums) mp[n/10] = n%10; // key=depth*10+pos, val=digit
    int total = 0;
    function<void(int,int)> dfs = [&](int key, int pathSum) {
        if (!mp.count(key)) return;
        pathSum += mp[key];
        int depth = key/10, pos = key%10;
        int lKey = (depth+1)*10 + 2*pos - 1;
        int rKey = (depth+1)*10 + 2*pos;
        if (!mp.count(lKey) && !mp.count(rKey)) total += pathSum;
        else { dfs(lKey, pathSum); dfs(rKey, pathSum); }
    };
    dfs(nums[0]/10, 0);
    return total;
}

# Python
def pathSum(nums):
    node_map = {}
    for n in nums:
        key, val = n // 10, n % 10
        node_map[key] = val

    total = [0]
    root_key = nums[0] // 10

    def dfs(key, path_sum):
        if key not in node_map:
            return
        path_sum += node_map[key]
        depth, pos = key // 10, key % 10
        l_key = (depth + 1) * 10 + 2 * pos - 1
        r_key = (depth + 1) * 10 + 2 * pos
        if l_key not in node_map and r_key not in node_map:
            total[0] += path_sum
        else:
            dfs(l_key, path_sum)
            dfs(r_key, path_sum)

    dfs(root_key, 0)
    return total[0]

// Java
Map<Integer, Integer> map = new HashMap<>();
int total = 0;
public int pathSum(int[] nums) {
    for (int n : nums) map.put(n/10, n%10);
    dfs(nums[0]/10, 0);
    return total;
}
void dfs(int key, int sum) {
    if (!map.containsKey(key)) return;
    sum += map.get(key);
    int d = key/10, p = key%10;
    int l = (d+1)*10 + 2*p - 1, r = (d+1)*10 + 2*p;
    if (!map.containsKey(l) && !map.containsKey(r)) total += sum;
    else { dfs(l, sum); dfs(r, sum); }
}

// JavaScript
function pathSum(nums) {
    const map = new Map();
    for (const n of nums) map.set(Math.floor(n/10), n%10);
    let total = 0;
    function dfs(key, sum) {
        if (!map.has(key)) return;
        sum += map.get(key);
        const d = Math.floor(key/10), p = key%10;
        const l = (d+1)*10 + 2*p - 1, r = (d+1)*10 + 2*p;
        if (!map.has(l) && !map.has(r)) total += sum;
        else { dfs(l, sum); dfs(r, sum); }
    }
    dfs(Math.floor(nums[0]/10), 0);
    return total;
}

Complexity

Time: O(n)
Space: O(n)