Leetcode 103: binary tree zigzag level tranversal(此题用DEQUE做终于做对了！！！)

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

这题 zigzag遍历输出一个tree，以前各种利用两个stack 倒来倒去的，虽然听老师说可以用deque来做，但是对deque操作不熟，一直搞不清楚怎么push 怎么pop，今天耐下心好好想了下，终于用deque做出来了，做完发现deque的做法很好，思路比两个stack思路清晰
首先，在奇数层和偶数层，打印的顺序是不同的，所以我们需要一个flag来标志是奇数层还是偶数层，每次分层打印，打印完所有的再进入下一层打印

其次，在奇数层和偶数层， 元素的push 和pop的方向是不同，如果使用deque，要满足下面的关系，如果pop_front取数据的话，explore 左右两个child必须要push_back， 如果pop_back取数据的话，explore左右两个child 必须要push_front，因为只有这样的顺序，才能导致元素不出现紊乱!

然后， 通过分析打印顺序， 我们可以发现，在1,3,5,7...这些层，需要从back pop, 并将explore的下一层的node 从左到右的顺序push到front, 在2,4,6,8...这些层，需要从front pop， 并将explore的下一层的node从右到坐的顺序push到back, 每一层打印完时，需要更新flag.


class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> rst;
        //sanity check
        if (root == NULL) return rst;
        deque<TreeNode*> explore;
        explore.push_back(root);
        int flag = 1;
        while (!explore.empty()) {
            int size1 = explore.size();//for print level by level
            vector<int> solu;
            if (flag == 1) {
                for (int i = 0; i < size1; i++) {
                    TreeNode* tmp = explore.back();
                    explore.pop_back();
                    solu.push_back(tmp->val);
                    if (tmp->left) explore.push_front(tmp->left);
                    if (tmp->right) explore.push_front(tmp->right);
                }
                rst.push_back(solu);
                flag = 0;
            }else if (flag == 0) {
                for (int i = 0; i < size1;i++) {
                    TreeNode* tmp = explore.front();
                    explore.pop_front();
                    solu.push_back(tmp->val);
                    if (tmp->right) explore.push_back(tmp->right);
                    if (tmp->left) explore.push_back(tmp->left);
                }
                rst.push_back(solu);
                flag = 1;
            }
        }
        return rst;
    }
};