LeetCode 102(Binary Tree Level Order Traversal, Python)

1. 문제 링크

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

- LeetCode

2. 문제 설명

• 이진 트리의 각 레벨마다 노드 값을 모두 담은 리스트를 반환하는 것
• 예시) 아래 트리가 주어지면 [[3],[9,20],[15,7]]를 반환

    3
   / \
  9  20
    /  \
   15   7

3. 처음 풀이

1. 재귀 함수 helper를 통한 DFS:
   • helper 함수는 현재 노드와 현재 레벨을 인자로 받음
   • 만약 현재 노드가 존재하지 않으면 함수를 종료
   • 현재 레벨이 결과 리스트에 존재하지 않으면, 새로운 리스트로 추가. 그렇지 않으면 이미 해당 레벨의 리스트가 존재하므로 해당 레벨의 리스트에 현재 노드의 값을 추가
2. 재귀 호출과 레벨 관리:
   • 왼쪽 자식 노드가 존재하면 helper 함수를 해당 자식 노드와 다음 레벨로 호출
   • 오른쪽 자식 노드가 존재하면 마찬가지로 helper 함수를 해당 자식 노드와 다음 레벨로 호출
   • 이렇게 하면 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]]:
        result = []

        def helper(root, level):
            if not root:
                return

            # 현재 레벨이 결과 리스트에 추가되어있지 않으면 새로운 리스트로 추가
            if len(result) < level + 1:
                result.append([root.val])
            else:
                # 이미 해당 레벨이 결과 리스트에 존재하면 해당 레벨 리스트에 값 추가
                result[level].append(root.val)
            
            # 왼쪽 자식 노드가 있으면 해당 노드로 재귀 호출
            if root.left:
                helper(root.left, level + 1)
            
            # 오른쪽 자식 노드가 있으면 해당 노드로 재귀 호출
            if root.right:
                helper(root.right, level + 1)
        
        # 루트부터 레벨 0으로 시작하여 순회
        helper(root, 0)

        return result

4. 다른 풀이

• 큐를 이용한 BFS 풀이

1. 루트 노드부터 시작하여 BFS를 수행
   • 큐에 초기에는 루트 노드를 담아둠
2. 큐에서 노드를 하나씩 꺼내면서 해당 노드의 값을 기록하고 자식 노드를 큐에 추가
   • 큐에서 노드를 꺼내어 현재 레벨의 값을 기록
   • 해당 노드의 왼쪽 자식이 있다면 큐에 추가
   • 해당 노드의 오른쪽 자식이 있다면 큐에 추가
3. 각 레벨별로 값을 기록한 리스트를 최종 결과 리스트에 추가
   • 현재 레벨의 값을 기록한 리스트를 최종 결과 리스트에 추가
4. 큐가 비어질 때까지 반복
   • 큐에서 모든 노드를 처리할 때까지 위의 과정을 반복

from collections import deque

# 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]]:
        if not root:
            return []

        result = []  # 최종 결과를 담을 리스트
        queue = deque([root])  # BFS를 위한 큐에 루트 노드 추가

        while queue:
            level_size = len(queue)
            level_values = []  # 현재 레벨의 노드 값을 담을 리스트

            for _ in range(level_size):
                node = queue.popleft()  # 큐에서 노드 추출
                level_values.append(node.val)  # 현재 레벨 리스트에 값 추가

                # 왼쪽 자식이 있으면 큐에 추가
                if node.left:
                    queue.append(node.left)
                
                # 오른쪽 자식이 있으면 큐에 추가
                if node.right:
                    queue.append(node.right)

            result.append(level_values)  # 현재 레벨의 값들을 최종 결과 리스트에 추가

        return result

 

5. 배운 점

• deque를 적극적으로 활용하자.