[LeetCode] 666. Path Sum IV 二叉树的路径和 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.

还是二叉树的路径之和,但树的存储方式变了,使用一个三位的数字来存的,百位是该结点的深度,十位是该结点在某一层中的位置,个位是该结点的值。

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] 112. Path Sum 路径和

[LeetCode] 113. Path Sum II 路径和 II

[LeetCode] 437. Path Sum III 路径和 III

All LeetCode Questions List 题目汇总

  

上一篇:.Net中的并行编程-2.ConcurrentStack的实现与分析


下一篇:LeetCode:简化路径【71】