forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathnested-list-weight-sum.py
More file actions
28 lines (26 loc) · 946 Bytes
/
nested-list-weight-sum.py
File metadata and controls
28 lines (26 loc) · 946 Bytes
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
#https://leetcode.com/problems/nested-list-weight-sum/
class Solution(object):
#DFS(Depth-First-Search)
#Efficiency: O(N), Space: O(D).
#N is the total element of the nestedList, D is the depth.
def depthSum(self, nestedList, weight=1):
counter = 0
for e in nestedList:
if e.isInteger():
counter+=(e.getInteger()*weight)
else:
counter+=self.depthSum(e.getList(), weight+1)
return counter
#BFS(Breadth-First-Search)
#Efficiency: O(N), Space: O(N).
def depthSum(self, nestedList):
counter = 0
queue = [(1, e) for e in nestedList]
while queue:
weight, e = queue.pop(0)
if e.isInteger():
counter += e.getInteger()*weight
else:
for child_list in e.getList():
queue.append((weight+1, child_list))
return counter