NeetCode 20번 알고리즘 : Breadth-First Search

Algorithm

 

Code

def bfs(root):
    queue = deque()

    if root:
        queue.append(root)
    
    level = 0
    while len(queue) > 0:
        print("level: ", level)
        for i in range(len(queue)):
            curr = queue.popleft()
            print(curr.val)
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        level += 1

 

만약, level을 keep track 하지 않아도 되는 경우는 다음과 같은 코드도 가능하다. (하지만 문제를 풀어보니 대부분 level을 track 하는게 많았다.

def bfs(root):
    queue = deque()

    if root:
        queue.append(root)
    
    while len(queue) > 0:
        curr = queue.popleft()
        print(curr.val)
        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)

 

Time Complexity

O(n)