# 666. Path Sum IV

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.
``````

``````class Solution {
public:
int pathSum(vector<int>& nums) {
if (nums.empty()) return 0;
int res = 0;
unordered_map<int, int> m;
for (int num : nums) {
m[num / 10] = num % 10;
}
helper(nums[0] / 10, m, 0, res);
return res;
}
void helper(int num, unordered_map<int, int>& m, int cur, int& res) {
int level = num / 10, pos = num % 10;
int left = (level + 1) * 10 + 2 * pos - 1, right = left + 1;
cur += m[num];
if (!m.count(left) && !m.count(right)) {
res += cur;
return;
}
if (m.count(left)) helper(left, m, cur, res);
if (m.count(right)) helper(right, m, cur, res);
}
};
``````

``````class Solution {
public:
int pathSum(vector<int>& nums) {
if (nums.empty()) return 0;
int res = 0, cur = 0;
unordered_map<int, int> m;
queue<int> q{{nums[0] / 10}};
for (int num : nums) {
m[num / 10] = num % 10;
}
while (!q.empty()) {
int t = q.front(); q.pop();
int level = t / 10, pos = t % 10;
int left = (level + 1) * 10 + 2 * pos - 1, right = left + 1;
if (!m.count(left) && !m.count(right)) {
res += m[t];
}
if (m.count(left)) {
m[left] += m[t];
q.push(left);
}
if (m.count(right)) {
m[right] += m[t];
q.push(right);
}
}
return res;
}
};
``````

Path Sum III

Binary Tree Maximum Path Sum

Path Sum II

Path Sum

https://discuss.leetcode.com/topic/101111/java-solution-represent-tree-using-hashmap

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation