The strategy here is to do a level order order traversal of the tree. You keep track of the level you're on and you use a boolean to determine which way to insert values into the list for the respective row

This solution takes linear time and space

```
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return [];
queue = [root];
currLevel = 1;
nextLevel = 0;
output = [];
level = [];
addRight = True;
while len(queue) != 0:
poppedNode = queue.pop(0);
currLevel -= 1;
if addRight:
level.append(poppedNode.val);
else:
level.insert(0,poppedNode.val);
if poppedNode.left:
nextLevel += 1;
queue.append(poppedNode.left);
if poppedNode.right:
nextLevel += 1;
queue.append(poppedNode.right);
if currLevel == 0:
currLevel = nextLevel;
nextLevel = 0;
output.append(level);
level = [];
if addRight:
addRight = False;
else:
addRight = True;
return output;
```