1def zigzag_level_order(root):
2 if not root:
3 return []
4 result = []
5 queue = [root]
6 left_to_right = True
7 while queue:
8 level_size = len(queue)
9 current_level = []
10 for _ in range(level_size):
11 node = queue.pop(0)
12 if left_to_right:
13 current_level.append(node.val)
14 current_level.insert(0, node.val)
15 if node.left:
16 queue.append(node.left)
17 if node.right:
18 queue.append(node.right)
19 result.append(current_level)
20 left_to_right = not left_to_right
21 return result