[leetcode 104] 이진 트리의 최대 깊이

문제

 

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

 

3

9 20

   15  7

 

 

문제를 풀기 전에 알고 가야 할 개념

• BFS
• 이진 트리

 

BFS란?

• Breadth First Search 의 약자로 너비 우선 탐색 알고리즘이다.
• 가까운 노드부터 탐색하는 알고리즘
• 주로 큐(선입선출 방식)인 자료구조를 이용하는 것이 정석
• 인접한 노드를 큐에 넣도록 알고리즘을 작성하면, 먼저 들어온 것이 먼저 나가게 되며 가까운 노드부터 탐색하게 된다.

 

기본 구조

from collections import deque # 큐 활용을  deque 라이브러리 활용

def bfs(graph, node, visited):

    queue = deque([node])
    visited[node] = True     # 현재 노드를 방문 처리

    # 큐가 빌 때까지 반복
    while queue:
    
        v = queue.popleft() # 큐에 삽입된 순서대로 노드 꺼내기

        print(v, end=' ')   # 탐색 순서 출력
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True

 

이진트리란

• 각각의 노드가 최대 2개의 자식 노드를 갖는 그래프 구조

 

풀이

 

from collections import deque

def maxDepth(self,root):
    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