103. Binary Tree Zigzag Level Order Traversal

Level Order Traversal (레벨 순회) : 각 깊이 별로 탐색하는 알고리즘

Solution

deque를 사용해 해결했다.
1. 큐의 길이를 저장해(size) 레벨이 바뀐 것을 구별한다.
2. 지그재그로 저장하기 위해서레벨이 바뀔 때마다 left를 바꿔준다.
3. 순서 큐에는 그대로 저장하되 정답 배열에만 역순으로 저장해주면 된다!

# 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
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = deque()
        ans = []
        left = True
        if root:
            q.append(root)
            while q:
                arr = deque()
                size = len(q)
                for i in range(size):
                    cur = q.popleft()
                    if cur.left: q.append(cur.left)
                    if cur.right: q.append(cur.right)
                    if left: arr.append(cur.val) 
                    else: arr.appendleft(cur.val) # 역순 저장
                ans.append(arr)
                left = not left
        return ans

시간 복잡도

deque의 삽입 연산은 모두 O(1)이고, 모든 노드를 돌기 때문에 시간 복잡도는 O(n) 이다.