103. Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

 

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # bfs => 큐로
        if not root:
            return []

        res = []

        que = deque([root])
        idx = 0
        while que:
            l = len(que)
            sub_res = []
            for i in range(l):
                node = que.popleft()
                sub_res.append(node.val)

                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)                
            
            if idx % 2 == 0: # 짝수면 
                res.append(sub_res) # 그대로 추가
            else: # 홀수면 
                res.append(sub_res[::-1]) # 역순으로 추가
            idx = (idx + 1) % 2
        
        return res