[LeetCode 103] Binary Tree Zigzag Level Order Traversal

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

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def zigzagLevelOrder(self, root):
        """
        BFS from the root.
        For each level, insert a list of values into the result
        """
        res = []
        if not root:
            return res
        q = [root]
        reverse = False
        while q:
            new_q = []
            if reverse:
                res.append([n.val for n in q][::-1])
            else:
                res.append([n.val for n in q])
            reverse = not reverse
            for node in q:
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right)
            q = new_q
        return res