All Articles

BFS에서 깊이 별로 작업하기

Binary Tree Level Order Traversal

Q102 Q637

BFS 는 BFS 인데 깊이 별로 무언가 하는 문제가 있었음그때는 깊이 별로 작업을 시작하기 전, 끝에 처리를 해주면 됨

기록해두고 싶은건 queue 모듈을 쓰기 싫을 때는 그냥 리스트에다 append 하고 한 번 reverse 해서 계속 pop 하면 나름 FIFO 느낌 나게 쓸 수 있다는거.

import queue

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:
            return res
        q = [root]
        while q:
            level_roots = []
            childs = []
            q.reverse()
            while q:
                node = q.pop()
                level_roots.append(node.val)
                if node.left:
                    childs.append(node.left)
                if node.right:
                    childs.append(node.right)
            res.append(level_roots)
            q = childs
        return res
Published 14 Apr 2018

If I keep marking the dots, someday they will 🔗🔗
Hyeungshik Jung on Twitter