[LeetCode] Python - 102. Binary Tree Level Order Traversal

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

Binary Tree Level Order Traversal - LeetCode

생각

이진 트리를 BFS 방식으로 탐색하는 문제입니다.

 

파이썬에서 BFS와 같이 큐를 사용해야할때 deque 자료구조를 사용하여 풀었습니다.

deque는 스택과 큐가 합쳐진 자료구조인데, pop 연산의 시간복잡도가 O(1) 이어서 코딩테스트 문제를 풀때 deque를 사용하는걸 추천합니다.

 

BFS로 탐색을 하되, 출력을 같은 레벨별로 묶어서 해줘야 하기때문에 각 레벨별 임시 배열 변수인 temp를 만들어주고, 큐 사이즈 만큼 반복문을 돌려 임시 배열에 노드들을 넣어줬습니다. 

 

Python Code

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: TreeNode) -> List[List[int]]:
        ans = []
        q = deque()
        q.append(root)
        while q:
            temp = []
            qSize = len(q)
            for i in range(qSize):
                now = q.popleft()
                if now:
                    q.append(now.left)
                    q.append(now.right)
                    temp.append(now.val)
            if temp:
                ans.append(temp)
            
        return ans