[DSA][Trees] 08. Binary Tree Level Order Traversal

LeetCode 102

 

08. 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가 null일 경우 빈 리스트를 반환하나요?

 

[아이디어]

- BFS 방식으로 트리를 순회하면서, 각 노드를 큐(deque)에 저장해 레벨 단위로 탐색한다.

 

 

[풀이 1] Breadth First Search

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        res = []
        q = deque()
        q.append(root)
        while q:
            tmp = []
            for i in range(len(q)):
                node = q.popleft()
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(tmp)
        
        return res

BFS 방식으로 트리를 레벨별로 순회하면서 각 레벨마다 큐에 들어 있는 노드들을 하나씩 꺼내어 그 노드들의 값을 임시 리스트(tmp)에 저장한다. 동시에 해당 노드의 왼쪽 자식과 오른쪽 자식이 존재하면 큐에 추가해서, 다음 레벨을 처리할 수 있게 한다. 이 과정을 큐가 빌 때까지 반복하며, 각 레벨의 노드 값을 결과 리스트에 순서대로 담는다.

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

트리의 모든 노드를 저장하므로 O(n)의 공간 복잡도를 가진다.