##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/666.html

# 666. Path Sum IV (Medium)

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
3. The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation:
The tree that the list represents is:
3
/ \
5   1

The path sum is (3 + 5) + (3 + 1) = 12.


Example 2:

Input: [113, 221]
Output: 4
Explanation:
The tree that the list represents is:
3
\
1

The path sum is (3 + 1) = 4.


Companies:
Alibaba

Related Topics:
Tree

Similar Questions:

## Solution 1.

• class Solution {
public int pathSum(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
Map<Integer, Integer> depthPositionValueMap = new HashMap<Integer, Integer>();
for (int num : nums) {
int depthPosition = num / 10, value = num % 10;
depthPositionValueMap.put(depthPosition, value);
}
int num0 = nums[0];
queue.offer(new int[]{num0 / 10, num0 % 10});
int sum = 0;
while (!queue.isEmpty()) {
int[] depthPositionValue = queue.poll();
int depthPosition = depthPositionValue[0], value = depthPositionValue[1];
int depth = depthPosition / 10, position = depthPosition % 10;
int leftDepthPosition = (depth + 1) * 10 + position * 2 - 1, rightDepthPosition = (depth + 1) * 10 + position * 2;
int left = depthPositionValueMap.getOrDefault(leftDepthPosition, -1), right = depthPositionValueMap.getOrDefault(rightDepthPosition, -1);
if (left < 0 && right < 0)
sum += value;
else {
if (left >= 0) {
int leftValue = left % 10;
queue.offer(new int[]{leftDepthPosition, value + leftValue});
} if (right >= 0) {
int rightValue = right % 10;
queue.offer(new int[]{rightDepthPosition, value + rightValue});
}
}
}
return sum;
}
}

############

class Solution {
private int ans;
private Map<Integer, Integer> mp;

public int pathSum(int[] nums) {
ans = 0;
mp = new HashMap<>(nums.length);
for (int num : nums) {
mp.put(num / 10, num % 10);
}
dfs(11, 0);
return ans;
}

private void dfs(int node, int t) {
if (!mp.containsKey(node)) {
return;
}
t += mp.get(node);
int d = node / 10, p = node % 10;
int l = (d + 1) * 10 + (p * 2) - 1;
int r = l + 1;
if (!mp.containsKey(l) && !mp.containsKey(r)) {
ans += t;
return;
}
dfs(l, t);
dfs(r, t);
}
}

• // OJ: https://leetcode.com/problems/path-sum-iv/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int pathSum(vector<int>& nums) {
unordered_map<int, int> m;
for (int n : nums) {
m[n / 10] = n % 10;
}
int sum = 0;
for (int n : nums) {
int d = n / 100, p = n / 10 % 10, v = m[d * 10 + p];
int left = (d + 1) * 10 + p * 2 - 1, right = left + 1;
if (m.count(left)) m[left] += v;
if (m.count(right)) m[right] += v;
if (m.count(left) == 0 && m.count(right) == 0) sum += v;
}
return sum;
}
};

• class Solution:
def pathSum(self, nums: List[int]) -> int:
def dfs(node, t):
if node not in mp:
return
t += mp[node]
d, p = divmod(node, 10)
l = (d + 1) * 10 + (p * 2) - 1
r = l + 1
nonlocal ans
if l not in mp and r not in mp:
ans += t
return
dfs(l, t)
dfs(r, t)

ans = 0
mp = {num // 10: num % 10 for num in nums}
dfs(11, 0)
return ans


• func pathSum(nums []int) int {
ans := 0
mp := make(map[int]int)
for _, num := range nums {
mp[num/10] = num % 10
}
var dfs func(node, t int)
dfs = func(node, t int) {
if v, ok := mp[node]; ok {
t += v
d, p := node/10, node%10
l := (d+1)*10 + (p * 2) - 1
r := l + 1
if _, ok1 := mp[l]; !ok1 {
if _, ok2 := mp[r]; !ok2 {
ans += t
return
}
}
dfs(l, t)
dfs(r, t)
}
}
dfs(11, 0)
return ans
}