103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution: BFS

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        lines = []
        q = [root]
        forward = True
        while q:
            new_q, line = [], []
            for node in q:
                if not node:
                    continue
                line.append(node.val)
                new_q.append(node.left)
                new_q.append(node.right)
            if not forward:
                line.reverse()
            if line:
                lines.append(line)
            forward = not forward
            q = new_q
        return lines