[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

- Problem

103. Binary Tree Zigzag Level Order Traversal

- 내 풀이 (BFS)

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        answer = []
        q = deque([root])
        direction = False

        while q:
            res = []
            direction = ~direction
            for _ in range(len(q)):
                node = q.popleft()

                if node:
                    res.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            
            if res:
                answer.append(res if direction else res[::-1])
        
        return answer

- 결과

level별로 순회하기 위해서 queue를 이용한 bfs 알고리즘을 이용한다.
또한, level이 바뀔 떄 마다 순회한 노드의 방향이 바뀌어야 하므로, while 문을 돌 때마다 direction의 방향을 바꿔준다.
while문 안의 for 문은 레벨에 따른 모든 노드의 개수를 뽑아내는 과정이다.

• 시간 복잡도: O(N) (N: 노드의 개수)
• 공간 복잡도: O(N)