Description#
If the depth of a tree is smaller than 5
, then this tree can be represented by an array of three-digit integers. For each integer in this array:
- The hundreds digit represents the depth
d
of this node where 1 <= d <= 4
. - The tens digit represents the position
p
of this node in the level it belongs to where 1 <= p <= 8
. The position is the same as that in a full binary tree. - The units digit represents the value
v
of this node where 0 <= v <= 9
.
Given an array of ascending three-digit integers nums
representing a binary tree with a depth smaller than 5
, return the sum of all paths from the root towards the leaves.
It is guaranteed that the given array represents a valid connected binary tree.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0666.Path%20Sum%20IV/images/pathsum4-1-tree.jpg)
Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/0666.Path%20Sum%20IV/images/pathsum4-2-tree.jpg)
Input: nums = [113,221]
Output: 4
Explanation: The tree that the list represents is shown.
The path sum is (3 + 1) = 4.
Constraints:
1 <= nums.length <= 15
110 <= nums[i] <= 489
nums
represents a valid binary tree with depth less than 5
.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int ans;
unordered_map<int, int> mp;
int pathSum(vector<int>& nums) {
ans = 0;
mp.clear();
for (int num : nums) mp[num / 10] = num % 10;
dfs(11, 0);
return ans;
}
void dfs(int node, int t) {
if (!mp.count(node)) return;
t += mp[node];
int d = node / 10, p = node % 10;
int l = (d + 1) * 10 + (p * 2) - 1;
int r = l + 1;
if (!mp.count(l) && !mp.count(r)) {
ans += t;
return;
}
dfs(l, t);
dfs(r, t);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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
}
|