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 D of this node, 1 <= D <= 4.
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.
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.
这个题目比较直接的方法是把二叉树建立起来，然后从根节点开始依次遍历各个叶子节点。这个方案会比较麻烦，因为涉及到回溯等等。更为简便的方法是从叶子节点往根节点遍历，把每个叶子节点遍历到根节点的和累加就行。
1. 找出所有的叶子节点。这个比较简单，遍历nums数组的每个元素，假设元素的值是abc，那么只要判断(a+1)(b*2)*或者(a+1)(b*2-1)*在不在nums数组中即可。【b*2中的*表示乘号，括号后面的*表示通配符】
def IsLeaf(self,nums,node):
dep = node/100
pos = (node%100)/10 next = (dep+1)*10 + pos*2
next2 = (dep+1)*10 + pos*2 -1
for i in nums:
if i/10 == next or i/10 == next2:
return False
return True
2. 找出叶子节点的父节点。这个同理，假设叶子节点的值是假设元素的值是abc，那么其父节点是(a-1)(b/2)*或者是(a-1)((b+1)/2)*。
def getParent(self,nums,node):
dep = node/100
pos = (node%100)/10
val = (node%100)%10
for i in nums:
if i/100 != dep -1:
continue
p = (i%100)/10
if p*2 == pos or p*2 == pos+1:
self.count += (i%100)%10
return i
return node
3.接下来就是开始求和了。
完整代码如下：
class Solution(object):
count = 0
def getParent(self,nums,node):
dep = node/100
pos = (node%100)/10
val = (node%100)%10for i in nums:
if i/100 != dep -1:
continue
p = (i%100)/10
if p*2 == pos or p*2 == pos+1:
self.count += (i%100)%10
return i
return node
def IsLeaf(self,nums,node):
dep = node/100
pos = (node%100)/10 next = (dep+1)*10 + pos*2
next2 = (dep+1)*10 + pos*2 -1
for i in nums:
if i/10 == next or i/10 == next2:
return False
return True def pathSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
maxDep = 0
for i in nums:
if maxDep < i /100:
maxDep = i/100
for i in nums:
if self.IsLeaf(nums,i) == False:
continue
else:
self.count += (i%100)%10
while True:
i = self.getParent(nums,i)
if i /100 == 1:
break return self.count
