⭐️ LeetCode 알고리즘 풀이 (with Python)

# Binary Tree Level Order Traversal

[Quetion]

LeetCode 102. Binary Tree Level Order Traversal

📌 접근법

[문제 이해]

• Binary Tree를 레벨 별로 노드 값을 리스트에 담아 반환

레벨 별로 노드 값을 알아야하기 때문에 Binary Tree BFS(너비 우선 탐색)를 활용하여 접근했다.
BFS 방법으로 순회하며 결과 리스트에 레벨 별로 리스트를 생성하고, 노드의 값을 추가해주는 법으로 구현했다.

💻 구현

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        l=[]
        self.level_search(root, l)
        return l

	# BFS
    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                if len(l) < level+1:
                    l.append([])   
                l[level].append(node.val)
                if node.left:
                    queue.append((node.left, level+1))
                if node.right:
                    queue.append((node.right, level+1))

Runtime: 40ms | Memory: 16.8MB
LeetCode 코드 중 Runtime 84%, Memory 99.7% 해당하는 결과

📌 로직 핵심

• BFS 함수 생성, 재귀 활용하여 Left, Right Tree 탐색
• Queue 자료구조를 활용하여 방문처리
• level 변수를 활용하여 레벨 별 리스트에 바로 접근하여 노드의 값 추가

📝 Binary Tree Level Order Traversal 회고

• 모든 트리를 순회하고, 결과 리스트에 레벨 별로 노드 값을 모두 저장해야하므로 시간복잡도와 공간복잡도 모두 O(N)이다.

• BFS 방법을 활용하여 레벨 별로 노드 값을 저장하는 간단한 응용 문제여서 비교적 쉽게 해결했다.

• BFS를 활용한 637. Average of Levels in Binary Tree를 먼저 해결해서 비교적 더 쉬웠던 것 같다.

• 문제를 해결하고 다른 솔루션을 보니 대부분 현재 코드와 비슷한 방식으로 해결해 나간 것을 확인했다. 그리고 특별한 추가적인 개선은 떠오르지 않아서 다른 수정은 진행하지 않았다.