## 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,#,#,15,7},
    3
/ \
9  20
/  \
15   7

return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]


### Analysis:

The idea is much similar to the previous question "Binary Tree Level Order Traversal", the only difference is the print order for each level. Note that we store the level order while traverse the tree, otherwise the print could be a mass. Just consider the order when pushing the values into the result vector. deque is a good STL container which can deal with double-end push and pop operation.

It is more easier to modify the "two queue" version of level-order travsersal. Details can be seen in the Python code.

### Code(C++):

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > res; //res vector
if (root!=NULL){
res.push_back(vector<int>(1,root->val)); // add root to the res
deque<TreeNode*> q1,q2;
vector<int> lev;
q1.push_back(root);
bool flag = false; //flag to decide the print order
while (true){
//level order traversal
while (!q1.empty()){
TreeNode* node = q1.front();
q1.pop_front();
if (node->left != NULL){q2.push_back(node->left);}
if (node->right != NULL){q2.push_back(node->right);}
}
if (q2.empty()){return res;}
q1 = q2;
//zigzag order print
while (!q2.empty()){
if (flag){
lev.push_back(q2.front()->val);
q2.pop_front();
}else{
lev.push_back(q2.back()->val);
q2.pop_back();
}
}
res.push_back(lev);
lev.clear();
flag = !flag;
}
}

return res;

}
};

### Code(Python):

# 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):
q1 = []
q2 = []
res = []
if root == None:
return res
q1.append(root)
l = []
forward = True
while True:
while len(q1) !=0 :
node = q1.pop(0)
if node.left != None:
q2.append(node.left)
if node.right != None:
q2.append(node.right)
if forward == True:
l.append(node.val)
else:
l.insert(0, node.val)
res.append(l)
l = []
q1 = q2
q2 = []
forward = not forward
if len(q1) == 0:
return res;