https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

zipzag.py

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        # evil test case
        if not root:
            return []
        
        # queue of tuple of (nodes to process, level they're on)
        # (start with the root)
        process = [ (root, 0) ]
        
        # the list to return later
        resp = []

        # normal BFS, add every level to the list
        while process:
            # dequeue next node and its level
            cur_node, level = process.pop(0)
            
            # grow the response array if needed for this level
            if level >= len(resp):
                resp.append([])
                
            # "visit" this node (add to process at current level)
            resp[level].append(cur_node.val)

            # enqueue its children to visit later
            children = [cur_node.left, cur_node.right]
            
            for child in children:
                if child:
                    process.append( (child, level+1) )      # increment current level
            
            
        # normal BFS is done, now go through and reverse the odd rows
        count = 0
        for row in resp:
            if count%2 == 1:
                resp[count] = resp[count][::-1]
            count += 1
        
        return resp