Python 알고리즘 인터뷰 - 문제 42. 이진 트리의 최대 깊이

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

 

문제

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

 

예제

입력 : [3, 9, 20, None, None, 15, 7]

출력 : 3

풀이

해당 문제는 BFS를 트리에 맞게 적용하여 순회하면서 각 계층에 depth를 계산하는 방법으로 진행한다. BFS는 부모에서 자식 순으로 왼쪽에서 오른쪽으로 탐색하는 방법으로 진행된다.

여기서 다음과 같이 각 계층 을 구분할 수 있는 방법이 있을까?

 

BFS는 queue사용하여 구현되며 코드는 다음과 같다.

root = create_tree_node([3, 9, 20, None, None, 15, 7])
queue = collections.deque([root])
visited = []
while queue:
    node = queue.popleft()
    visited.append(node.val)
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

먼저 queue를 root 노드 0으로 초기화한다.

0을 pop한 후 left, right를 노드가 존재 시 queue에 push 한다.

 

이 후 먼저 들어간 9를 pop한 후 left, right를 추가한다. 9는 자식 노드가 없으므로 queue에 데이터가 들어가지 않는다. 20의 경우는 자식 노드 15, 7이 존재하므로 queue에 추가한다.

해당 진행 순서를 자세히 보면 queue에 길이만큼 queue에 데이터를 pop하고 자식 노드를 추가하면, depth를 나눌 수 있 수 있다. 

이를 통해 코드를 구현하면 다음과 같다.

def maxDepth(root):
    if root is None:
	return 0
    queue = collections.deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth