103 Binary Tree Zigzag Level Order

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).

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]
]

Different from the regular level order traversal, we can do the following method in order to present the binary tree in a zigzag format,

1. Have a binary flag (boolean variable) to distinguish whether it's leftToRight or rightToLeft
2. Update flag after each level
3. have two lists, one for current level, one for the next level