**Solution**

**Binary Tree Zigzag Level Order Traversal** https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

**Algorithm**

- Use 2 stacks and alternate the order of adding to these stacks.

```
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
s1_rl, s2_lr = [root], []
output, rl = [], True
while s1_rl or s2_lr:
op = []
if rl:
for _ in range(len(s1_rl)):
x = s1_rl.pop()
op.append(x.val)
if x.left:
s2_lr.append(x.left)
if x.right:
s2_lr.append(x.right)
else:
for _ in range(len(s2_lr)):
x = s2_lr.pop()
op.append(x.val)
if x.right:
s1_rl.append(x.right)
if x.left:
s1_rl.append(x.left)
rl = not rl
output.append(op)
return output
```