方法一：单队列

1.结题思路

首先题目是之字形层序遍历，所以不难想到，在实现层序遍历的基础上，对树高度判断奇偶，奇数层后插入容器实现从左到右遍历，偶数层相反，前插容器实现从右到左遍历，或向右遍历后用reverse函数进行翻转。

2.解法

在用队列层序遍历的基础上，根据高度layer，实现容器的前插后插，即为从左到右遍历与从右到左遍历。

3.图解

4.具体代码

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    vector<vector<int> >ans;
    if(root==NULL)return ans;
    queue<TreeNode*>q;//遍历所有树节点 
    q.push(root);
    int layer=0; 
    while(!q.empty()){            
        vector<int>temp;//存储当前层所有树结点权值 
        int size=q.size();//当前层节点数 
        layer++; 
        for(int i=0;i<size;i++){//遍历当前层 
            TreeNode* p=q.front();q.pop();//从队列中取出一个当前层结点 ,然后访问它 
            if(layer&1)temp.push_back(p->val);//根据树的层数前插或后插 即实现 之字形层次遍历 
            else temp.insert(temp.begin(),p->val);
            if(p->left!=NULL)q.push(p->left);//将下一层孩子入队 
            if(p->right!=NULL)q.push(p->right);                
        } 
        ans.push_back(temp); 
    }
    return ans;
}

5.时间复杂度和空间复杂度分析

时间复杂度为O(n)：n是二叉树中的节点个数。时间复杂度为二叉树层数*每层树节点数，每层的访问操作复杂度为O(1);n个结点的二叉树最多有n层，一层一个结点;最少层为log2(n + 1)上取整，也就是同样多结点完全二叉树的高度,时间复杂度为O(n);

空间复杂度也为O(n)：n是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过n。

方法二：双栈

1.结题思路

在层序遍历的基础上，根据题意每一层遍历方向都和下一层相反，利用栈先进后出的特性，每当要访问下一层的时候，都利用栈翻转一下访问顺序。

2.解法

首先根结点入栈s1，然后不断令s1栈顶元素出栈，并访问它，同时令栈顶元素的孩子结点按照先左孩子后右孩子的顺序入栈s2；接下来在栈s2中，不断令s2栈顶元素出栈，并访问它，因为栈先进后出的特性，出栈序列变为先右孩子后左孩子，即实现从右到左顺序访问，访问栈顶元素的同时，也将栈顶元素的孩子结点按照先右孩子后左孩子的顺序入栈s1；易知s1再出栈栈顶元素并往s1入栈孩子结点即为向右访问，s2则为向左访问。

当栈s1，s2均为空时，即为访问完所有树结点时。

3.图解

4.具体代码

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    vector<vector<int> >ans;
    if(root==NULL)return ans;
    stack<TreeNode*>s1,s2;
    s1.push(root);
    while(!s1.empty()||!s2.empty()){
        vector<int>temp;//存储当前层所有树结点权值
        while(!s1.empty()){
            TreeNode* p=s1.top();s1.pop();//取栈顶元素访问并出栈
            temp.push_back(p->val);
            if(p->left!=NULL)s2.push(p->left);//孩子结点入另一个栈
            if(p->right!=NULL)s2.push(p->right);
        }
        if(!temp.empty())ans.push_back(temp);//将当前层的遍历结果加入结果 
        temp.clear();
        while(!s2.empty()){
            TreeNode* p=s2.top();s2.pop();//取栈顶元素访问并出栈
            temp.push_back(p->val);
            if(p->right!=NULL)s1.push(p->right);//孩子结点入另一个栈    
            if(p->left!=NULL)s1.push(p->left);
        }
        if(!temp.empty())ans.push_back(temp);//将当前层的遍历结果加入结果              

    }
    return ans;
}

5.时间复杂度和空间复杂度分析

时间复杂度为O(n)：其中n是二叉树中的节点个数。每个节点访问一次，使用栈的结构，对每个节点出栈入栈的时间复杂度是O(1)，因此总时间复杂度是O(n)。

空间复杂度为O(n)：其中n是二叉树中的节点个数。空间复杂度取决于栈与vector开销，栈与vector中的节点个数不会超过 n。