모각코 2주차 bfs

def bfs(graph, start_node):
    visit = list()
    queue = list()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
    return visit

 

관련 문제

199. Binary Tree Right Side View

class Solution(object):
    def rightSideView(self, root):
        def bfs(root, level, rightSide):
            if not root: return
            if level == len(rightSide): rightSide.append(root.val)
            bfs(root.right, level+1, rightSide)
            bfs(root.left, level+1, rightSide)
        rightSide = []
        bfs(root, 0, rightSide)
        return rightSide

관련문제2

1161. Maximum Level Sum of a Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        max, level, maxLevel = -float('inf'), 0,0
        q= collections.deque()
        q.append(root)
        while q:
            level += 1
            sum = 0
            for _ in range(len(q)):
                node = q.popleft()
                sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if max < sum:
                max, maxLevel = sum, level
        return maxLevel

 

dfs 로 해당 문제 다시 풀기

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node, list, level):
            if not node: return
            if len(list) == level: list.append(node.val)
            else: list[level] += node.val
            dfs(node.left, list, level + 1)
            dfs(node.right, list, level + 1)
        list = []
        dfs(root, list, 0)
        return 1 + list.index(max(list))