[leetcode] 104. 이진 트리의 최대 깊이 (Maximum Depth of Binary Tree)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

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

 

 

입출력 예시

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

 

Example 2:

Input: root = [1,null,2]
Output: 2

 

 

풀이

def max_depth(list):
	# 데크를 이용해 root노드를 담아준다.
    q = deque([root])
    
    # 깊이 초기화
    depth = 0

    while q:
        depth += 1
        for _ in range(len(q)):
            cur = q.popleft()
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

    return depth

 

큐를 이용하는 BFS 방식과 크게 다르지 않고, 코드도 어렵지 않다. 디테일 한 설명은 생략하기로 한다.

 

 

---

마치며

직접 구현하는건 어렵지만 개념이나 흐름 자체는 크게 어렵지 않아서 이해하는 데 오래걸리지 않았다. 언제쯤 직접 구현 슉슉 하는 날이 올까...