Four python solutions
Approach - 1\nUsing single ended queue and reverse. Although we are using deque we are utilizing only single ended queue functionality here.\npython\ndef zigzag
#### Approach - 1\nUsing single ended queue and reverse. Although we are using `deque` we are utilizing only single ended queue functionality here.\n```python\ndef zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n\tif not root: return []\n\tqueue = collections.deque([root])\n\tres = []\n\teven_level = False\n\twhile queue:\n\t\tn = len(queue)\n\t\tlevel = []\n\t\tfor _ in range(n):\n\t\t\tnode = queue.popleft()\n\t\t\tlevel.append(node.val)\n\t\t\tif node.left:\n\t\t\t\tqueue.append(node.left)\n\t\t\tif node.right:\n\t\t\t\tqueue.append(node.right)\n\t\tif even_level:\n\t\t\tres.append(level[::-1])\n\t\telse:\n\t\t\tres.append(level)\n\t\teven_level = not even_level\n\treturn res\n```\n\n#### Appraoch - 2\nUsing single ended queue and initializing array instead of reversing. \n```python\ndef zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n\tif not root: return []\n\tqueue = collections.deque([root])\n\tres = []\n\teven_level = False\n\twhile queue:\n\t\tn = len(queue)\n\t\tlevel = [0] * n # initalize the array since we know the length\n\t\tfor i in range(n):\n\t\t\tnode = queue.popleft()\n\t\t\tif node.left:\n\t\t\t\tqueue.append(node.left)\n\t\t\tif node.right:\n\t\t\t\tqueue.append(node.right)\n\t\t\tif even_level:\n\t\t\t\tlevel[n-1-i] = node.val\n\t\t\telse:\n\t\t\t\tlevel[i] = node.val\n\t\tres.append(level)\n\t\teven_level = not even_level\n\n\treturn res\n```\n#### Approach - 3\nUsing the double ended queue functionality. We pop from left in odd levels and pop from right in even levels. Trick is to flip the order of left and right when we are appending from left. \n```python\ndef zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n\tif not root: return []\n\tqueue = collections.deque([root])\n\tres = []\n\teven_level = False\n\twhile queue:\n\t\tn = len(queue)\n\t\tlevel = []\n\t\tfor i in range(n):\n\t\t\tif even_level:\n\t\t\t\t# pop from right and append from left.\n\t\t\t\tnode = queue.pop()\n\t\t\t\t# to maintain the order of nodes in the format of [left, right, left, right] \n\t\t\t\t# we push right first since we are appending from left\n\t\t\t\tif node.right: queue.appendleft(node.right)\n\t\t\t\tif node.left: queue.appendleft(node.left)\n\t\t\telse:\n\t\t\t\t# pop from left and append from right\n\t\t\t\tnode = queue.popleft()\n\t\t\t\t# here the order is maintained in the format [left, right, left, right] \n\t\t\t\tif node.left: queue.append(node.left)\n\t\t\t\tif node.right: queue.append(node.right)\n\t\t\tlevel.append(node.val)\n\t\tres.append(level)\n\t\teven_level = not even_level\n\treturn res\n```\n\n#### Approach - 4\nUsing deque for each level instead of list.\n```python\ndef zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n    if not root: return []\n    res = []\n    queue = collections.deque([root])\n    even_level = False\n    while queue:\n        n = len(queue)\n        level = collections.deque()\n        for _ in range(n):\n            node = queue.popleft()\n            if even_level:\n                level.appendleft(node.val)\n            else:\n                level.append(node.val)\n            if node.left:\n                queue.append(node.left)\n            if node.right:\n                queue.append(node.right)\n        res.append(list(level))\n        even_level = not even_level\n    return res\n```
['Queue', 'Python', 'Python3']