[LeetCode]Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

Binary Tree Level Order Traversal - LeetCode

 

문제 분석

주어진 이진 트리에서 동일한 레벨에 있는 노드들을 그룹화 하는 문제입니다.

 

처음 시도한 답안 - DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        def dfs(root, level, answer):
            if not root:
                return answer

            if level in answer:
                answer[level].append(root.val)
            else:
                answer[level] = [root.val]

            dfs(root.left, level+1, answer)
            dfs(root.right, level+1, answer)

            return answer

        answer = dfs(root, 0, {})

        return list(answer.values())

접근 방법

1. DFS 알고리즘을 이용해 트리를 재귀적으로 탐색합니다.
2. DFS 내부에서
   1. 딕셔너리를 활용해 level을 키로하고, value로 등장한 노드들의 값을 append 합니다.
   2. 왼쪽과 오른쪽에 대해서 재귀적으로 호출합니다.
3. 저장된 answer 딕셔너리에서 values만 추출하면 그룹화할 수 있습니다.

DFS에 익숙해진 탓인지 트리를 탐색하는 방법은 자연스럽게 DFS를 선택했습니다. 다만 깊이 우선 탐색의 경우 레벨별로 순차적으로 탐색하는게 아니기 때문에 dict 자료를 이용해 동일한 레벨의 값들을 그룹화 해주었습니다.

 

모든 노드를 탐색하는 것이기에 DFS, BFS 큰 차이는 없다고 생각하지만 일반적으로 BFS가 더 적합한 솔루션인 것 같아 찾아보았습니다.

 

두번째로 시도한 답안 - BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # BFS

        if not root:
            return root

        queue = [root]
        answer = []

        # queue가 있는 동안 탐색 (모든 노드를 탐색하는 동안)
        while queue:
            next_queue = []
            level = []

            for root in queue:
                # 동일한 레벨에 있는 값들 push
                level.append(root.val)

                # 왼쪽 자식 노드가 존재하면, 다음 큐에 넣음 
                if root.left:
                    next_queue.append(root.left)
                # 오른쪽 자식 노드가 존재하면, 다음 큐에 넣음
                if root.right:
                    next_queue.append(root.right)
                    
            answer.append(level)
            # 다음 레벨을 탐색할 queue로 할당
            queue = next_queue

        return answer

접근 방법

1. queue가 있는 동안 탐색합니다. (모든 노드를 탐색하는 동안)
   1. next_queue에는 다음 레벨에 있는 트리들을 넣어주는 용도로 사용됩니다.
   2. level에는 동일한 레벨에 있는 값들을 기록하기 위한 용도입니다.
   3. queue를 순회합니다.
      1. 동일한 레벨에 있는 값들을 level 리스트에 push 합니다.
      2. 만약 왼쪽 자식 노드가 존재하면 next_queue에 넣어줍니다.
      3. 만약 오른쪽 자식 노드가 존재하면 next_queue에 넣어줍니다.
   4. 정답에 그룹화된 level을 넣어줍니다.
   5. queue에는 다음 레벨의 트리들이 들어있는 next_queue로 할당합니다.
   6. 반복합니다.

BFS와 큐 자료구조를 활용해서 레벨별로 순차적으로 탐색을 진행할 수 있습니다. 아직까지는 BFS 문제를 많이 풀어보지 않아서 어색하지만 상황에 맞게 선택하면 좋을 것 같습니다.