[LeetCode 해석 및 풀이] 102. Binary Tree Level Order Traversal(이진 트리 수준 순서 탐색)

LeetCode 문제 해석 및 풀이 방법

문제 102. Binary Tree Level Order Traversal(이진 트리 수준 순서 탐색)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

 

한글

이진 트리의 root 주어지면 해당 노드 값의 레벨 순서 순회를 반환합니다. (즉, 왼쪽에서 오른쪽으로, 레벨별로).

 

제한조건

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

 

입출력 예

입력	출력
root = [3,9,20,null,null,15,7]	[[3],[9,20],[15,7]]
root = [1]	[[1]]
root = []	[]

 

해답 및 해설

파이썬 (Python)

깊이 우선 탐색(DFS)를 이용한 방법

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        answer = []
        def addLevelDFS(root, level):
            if not root:
                return

            nonlocal answer

            while level >= len(answer):
                answer.append([])
            answer[level].append(root.val)

            addLevelDFS(root.left, level+1)
            addLevelDFS(root.right, level+1)
        
        addLevelDFS(root, 0)
        
        return answer

재귀를 이용하여 깊이 우선 탐색을 하되, 다음 단계로 넘어갈 때마다 레벨이 1씩 추가됨을 명시하는 방식. 이렇게 하면 각 노드가 몇 번째 레벨인지 알 수 있게 된다.

 

너비 우선 탐색(BFS)을 이용한 방법

from queue import Queue

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        answer = []
        queue_now = Queue()
        queue_now.put(root)
        queue_future = Queue()

        while not queue_now.empty():
            answer.append([])

            while not queue_now.empty():
                now_node = queue_now.get()
                answer[-1].append(now_node.val)

                if now_node.left:
                    queue_future.put(now_node.left)
                if now_node.right:
                    queue_future.put(now_node.right)
                
            queue_now, queue_future = queue_future, queue_now
        
        return answer

너비 우선 탐색으로 레벨마다 큐를 만들고, 현재 레벨 큐에 있는 노드들을 탐색하여 다음 레벨 큐의 노드에 넣고, 레벨 탐색이 끝나면 다음 레벨 큐를 불러오는걸 반복하는 방식. 

 

시간이 다른 풀이보다 훨씬 오래 걸리는 것으로 나왔는데, 아마 큐를 계속해서 서로 바꾼다는 점, 그리고 deque라는 라이브러리와 인덱스 탐색 방식을 쓰지 않는다는 점 때문이 아닐까 싶다...