思路：

二叉树层序遍历使用BFS即可，本题需要之字形层序遍历，即变换每层遍历的方向，用一个标识记住方向。

方法一：使用队列

1.用一个队列维护树的BFS遍历。
2.用一个bool变量left_to_right表示当前层是从左往右遍历，还是从右往左。

代码实现

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        if(root==nullptr) 
            return ans;
        queue<TreeNode*> q;
        q.push(root);
        //记录当前层遍历的方向
        bool left_to_right=true;
        while(!q.empty()){
            //sz记录当前层的数目
            int sz=q.size();
            //cur是每一层的遍历结果
            vector<int> cur;
            while(sz--){
                TreeNode* tmp=q.front();
                cur.push_back(tmp->val);
                q.pop();
                if(tmp->left)
                    q.push(tmp->left);
                if(tmp->right)
                    q.push(tmp->right);
            }
            if(left_to_right==true){
                ans.push_back(cur);
                left_to_right=false;
            }else{
                reverse(cur.begin(),cur.end());
                ans.push_back(cur);
                left_to_right=true;
            }        
        }
        return ans;
    }
};

示意图如下：

复杂度分析

时间复杂度：O(n), n是二叉树节点数量，因为BFS对每个节点访问一次。
空间复杂度：O(n)，空间复杂度来源于队列中存储节点所需要的最大空间，该值最大为(n+1)/2，当树为满二叉树时。

方法二：使用双端队列

基本思路与方法一类似。不同之处在于使用双端队列dequeue,记录下每一层的遍历方式，可以直接进行插入队首和插入队尾的操作。

代码实现

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        if(root==nullptr) 
            return ans;
        deque<TreeNode*> q;
        q.push_back(root);
        //记录当前层遍历的方向
        bool left_to_right=true;
        while(!q.empty()){
            //sz记录当前层的数目
            int sz=q.size();
            //cur是每一层的遍历结果
            vector<int> cur;
            TreeNode* tmp;
            while(sz--){
                //从左向右遍历，那么生成下一层的方式是先左子树，再右子树，插入队尾。
                if(left_to_right){
                    tmp=q.front();
                    q.pop_front();
                    if(tmp->left)
                        q.push_back(tmp->left);
                    if(tmp->right)
                        q.push_back(tmp->right);
                }
                //从右往左遍历，那么生成下一层的方式是先右子树，再左子树，插入队首。
                else{
                    tmp=q.back();
                    q.pop_back();
                    if(tmp->right)
                        q.push_front(tmp->right);
                    if(tmp->left)
                        q.push_front(tmp->left);
                }
                cur.push_back(tmp->val);
            }
            left_to_right=!left_to_right;
            ans.push_back(cur);                  
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)，与方法一相同。
空间复杂度：O(n)，与方法一相同。