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:
- The hundreds digit represents the depth
Dof this node,1 <= D <= 4. - The tens digit represents the position
Pof this node in the level it belongs to,1 <= P <= 8. The position is the same as that in a full binary tree. - The units digit represents the value
Vof 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.
还是二叉树的路径之和，但树的存储方式变了，使用一个三位的数字来存的，百位是该结点的深度，十位是该结点在某一层中的位置，个位是该结点的值。
Python：
class Solution(object):
def pathSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
class Node(object):
def __init__(self, num):
self.level = num/100 - 1
self.i = (num%100)/10 - 1
self.val = num%10
self.leaf = True def isParent(self, other):
return self.level == other.level-1 and \
self.i == other.i/2 if not nums:
return 0
result = 0
q = collections.deque()
dummy = Node(10)
parent = dummy
for num in nums:
child = Node(num)
while not parent.isParent(child):
result += parent.val if parent.leaf else 0
parent = q.popleft()
parent.leaf = False
child.val += parent.val
q.append(child)
while q:
result += q.pop().val
return result
C++：
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);
}
};
类似题目：
[LeetCode] 113. Path Sum II 路径和 II
[LeetCode] 437. Path Sum III 路径和 III
All LeetCode Questions List 题目汇总