Binary Tree Zigzag Level Order Traversal

1def zigzagLevelOrder(root):
2  if not root:
3    return []
4
5  result = []
6  queue = [root]
7  level = 0
8
9  while queue:
10    level_size = len(queue)
11    current_level = []
12
13    for i in range(level_size):
14      node = queue.pop(0)
15      current_level.append(node.val)
16
17      if node.left:
18        queue.append(node.left)
19      if node.right:
20        queue.append(node.right)
21
22    # Reverse if odd level (right-to-left)
23    if level % 2 == 1:
24      current_level.reverse()
25
26    result.append(current_level)
27    level += 1
28
29  return result