339. Nested List Weight Sum

[tech-cow]

第一遍

DFS

时空复杂： O(N) | O(depth)

知道Recursion
Can't Convert, DFS实现需要走一遍Python Tutor, Bottom-up 方法有点绕脑子。

class Solution(object):
    def depthSum(self, nestedList):
        return self.dfs(nestedList, 1)
    

    def dfs(self, nestedList, depth):
        res = 0
        for element in nestedList:
            if element.isInteger():
                res += element.getInteger() * depth
            else:
                res += self.dfs(element.getList(), depth + 1)
        return res

BFS

时空复杂： O(N) | O(N)

不知道initialize的时候enqueue什么，并且在expand的时候没有写for loop

from collections import deque
class Solution(object):
    def depthSum(self, nestedList):
        
        # 不知道enqueue什么。
        queue = deque([(1, element) for element in nestedList])
        res = 0
        
        while queue:
            depth, node = queue.popleft()
            
            if node.isInteger():
                res += node.getInteger() * depth
            else:
                # Enqueue这出错, 没写Tuple， 之后写成了depth，没写成depth + 1。然后没有写for loop。。。。。。。
                for children_node in node.getList():
                    queue.append((depth + 1, children_node))
            
        return res