이진 트리의 최대 깊이

https://leetcode.com/problems/maximum-depth-of-binary-tree/

 

Maximum Depth of Binary Tree - LeetCode

 깊이는 여러 가지 방법이 있지만 여기서는 BFS로 풀이해 보겠다. DFS는 스택, BFS는 큐를 사용하여 구현한다.

 큐 변수에는 현재 깊이 depth에 해당하는 모든 노드가 들어 있고, queue.popleft()로 하나씩 끄집어 내면서 cur_root.has_child()로 자식 노드가 있는지 여부를 판별한 후 자식 노드를 다시 큐에 삽입한다.

 

 그렇다면 동일한 큐에 삽입하다 보니 행여나 자식 노드가 부모 노드와 섞이진 않을까? 아마 섞일 것이다. 그러나 이 for 반복문에서는 자식 노드가 추출되는 일은 없을 것이다. 왜냐면 처음 for 문 진입 시 부모 노드의 길이 len(queue) 만큼만 반복하도록 선언했기 때문이다.

 

# Definition for a binary tree node.
# 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: Optional[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)
                    
        return depth