[알고리즘] 이진 트리의 최대 깊이

이진 트리의 최대 깊이

책 풀이

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0

        queue = collections.deque([root])
        depth = 0

        while queue:
            depth += 1
            # 큐 연산 추출 노드이 자식 노드 삽입
            for _ in range(len(queue)):
                cur_root = queue.popleft()
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        # BFS 반복 횟수 == 깊이
        return depth

큐를 이용해서 한 층의 자식 노드들을 모두 담는 것이다. 큐가 한번 돌 때마다 depth가 1씩 깊어진다. 주의해야할 점은 for 문 진입 시 부모 노드의 길이 len(queue)만큼만 반복되도록해서, for 반복문에서 자식 노드가 추출되지 않도록 하는 것이다.