题目：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

我的方法一：广度优先搜索

思路：这个和二叉树的层序遍历是用队列，有一点区别就是奇数层从右往左；所以奇数层往结果vector插入时，从vector头往尾插；偶数层插入时，从vector尾往头插；
方法较简单，代码如下：

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root){
            return ret;
        }

        queue<TreeNode*> q;
        q.push(root);

        int level_index = 0;
        int level_size = 0;

        while(!q.empty()){
            level_size = q.size();
            vector<int> level_result;
            level_result.resize(level_size);

            if(level_index%2 == 1){
                while(level_size > 0){
                    level_result[level_size-1] = q.front()->val;
                    level_size--;

                    if(q.front()->left){
                        q.push(q.front()->left);
                    }
                    if(q.front()->right){
                        q.push(q.front()->right);
                    }
                    q.pop();
                }
            }else{
                for(int i = 0; i<level_size; i++){
                    level_result[i] = q.front()->val;
                    if(q.front()->left){
                        q.push(q.front()->left);
                    }
                    if(q.front()->right){
                        q.push(q.front()->right);
                    }
                    q.pop();
                }
            }

            level_index++;
            ret.push_back(level_result);
        }

        return ret;
    }
};