103. Binary Tree Zigzag Level Order Traversal.md

103. Binary Tree Zigzag Level Order Traversal (Medium)

[tag] BFS, binary tree

• same way of using queue, but different order of appending to results.
• use a deque for appending result in each level as well
• use a variable for direction.

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        RIGHT = 1
        LEFT = 0
        direction = RIGHT
        tree_queue = deque([root])
        ans = []
        while tree_queue:
            cur_len = len(tree_queue)
            cur_level = deque()
            for _ in range(cur_len):
                cur_node = tree_queue.popleft()
                if direction == RIGHT:
                    cur_level.append(cur_node.val)
                else:
                    cur_level.appendleft(cur_node.val)
                if cur_node.left:
                    tree_queue.append(cur_node.left)
                if cur_node.right:
                    tree_queue.append(cur_node.right)
            ans.append(cur_level)
            direction = not direction
        return ans