[알고리즘] Leetcode #104 이진 트리의 최대 깊이 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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

Example 3:

Input: root = [] Output: 0

Example 4:

Input: root = [0] Output: 1

 

Constraints

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

 

Code

def maxDepth(self, root):
    if root is None:
        return 0
    
    queue = collections.deque([root]) # 양방향 추출이 빈번한 경우 유리
    depth = 0
    
    while queue: # BFS
        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를 0으로 초기화한 후, 전체 root를 차례로 돌면서 자식노드가 있을 경우 queue에 다시 append한다. queue가 존재할 때까지 while문을 반복하여 얻은 depth (while문 실행 횟수)가 총 깊이가 되므로 이를 그대로 return하면 tree의 최대 깊이를 반환한다. 

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)