42. Maximum Depth of Binary Tree

리트코드

• 이진 트리의 최대 깊이를 구하라.

"트리는 순환 구조를 갖지 않는 그래프이다."

1. 반복 구조로 BFS 풀이

# 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: 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

• 깊이를 측정하는 방법은 다양하지만 여기서는 BFS (너비 우선 탐색)으로 풀이한다.

  • BFS는 재귀가 아닌 반복 구조로 풀이할 수 있다.

• 먼저 큐를 선언하고 풀이할 준비를 한다.

  • 파이썬에서 큐는 일반적인 리스트로도 모든 연산이 가능하다.

  • 하지만, 데크 자료형을 사용하면 이중 연결 리스트로 구성되어 있기 때문에 큐와 스택 연산을 모두 자유롭게 활용 가능할 뿐만 아니라 양방향 모두 O(1)에 추출할 수 있어 좋은 성능을 보인다

    • 실제로도 양방향 추출이 빈번할 경우, 리트코드의 실행 속도 또한 데크가 리스트에 비해 훨씬 빠르다.

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

  • 여기서 .has_child()와 .child()는 전부 이해를 돕기 위한 수도코드다.

• 동일한 큐에 삽입하다 보니 행여나 자식 노드가 부모 노드와 섞이진 않을까? 아마 섞일 것이다.

  • 그러나, 이 for 반복문에서는 자식 노드가 추출되는 일은 없을 것이다.
    처음 for문 진입 시, 부모 노드의 길이 len(queue)만큼만 반복하도록 선언했기 때문이다.

  • 부모 노드가 모두 추출된 이후에는 for문을 빠져 나가게 되고, 다시 한바퀴 돌아 while queue 구문에서 이번에는 다음 번 깊이의 노드 반복이 진행될 것이다.

• queue.append(cur_root.child)로 깊이별 큐에 삽입되는 자식 노드를 도식화 하면 다음과 같다.
  

  • 깊이별로 노드가 추가되는 BFS 구조를 나타낼 수 있다.

  • 예제의 입력값이 [3,9,20,null,null,15,7]일 때, depth가 1이면 [3],
    2이면 [9, 20],
    3이면 [15, 7]이 삽입되어 처리된다.

  • 깊이 depth는 while 구문의 반복 횟수이므로 BFS에서 반복 횟수는 곧 높이가 된다.

• 반복 횟수를 리턴하면 최종 결과를 구할 수 있다.