题目的主要信息：

• 给定一个二叉树，返回该二叉树的之字形层序遍
• 第一层从左向右，下一层从右向左，一直这样交替
• 进阶要求：空间复杂度：$O(n)O(n)$，时间复杂度：$O(n)O(n)$

方法一：非递归层次遍历

具体做法：

按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用flag标记，第一层为false，之后每到一层取反一次，如果该层的flag为true，则记录的数组整个反转即可。

但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：

• 当根节点进入队列时，队列长度为1，第一层结点数也为1
• 若是根节点有两个子节点，push进队列后，队列长度为2，第二层结点数也为2；若是根节点一个子节点，push进队列后，队列长度为为1，第二层结点数也为1.
• 由此，我们可知，每层的结点数等于进入该层时队列长度，因为刚进入该层时，这一层每个结点都会push进队列，而上一层的结点都出去了。

具体如图所示，下图展示了如何按层打印二叉树：

综上，反过来，每次只要在队列长度内循环，必定是一层，一层访问完毕再更新队列长度即可。有了上述的每层的输出数组，按照上述规则只要根据flag标记在偶数层反转该数组即可。

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        TreeNode* head = pRoot;
        vector<vector<int> > res;
        if(head == NULL)
            return res; //如果是空，则直接返回空vector
        queue<TreeNode*> temp; //队列存储，进行层次遍历
        temp.push(head);
        TreeNode* p;
        bool flag = true;
        while(!temp.empty()){
            vector<int> row;  //记录二叉树的某一行
            int n = temp.size();
            flag = !flag; //奇数行反转，偶数行不反转
            for(int i = 0; i < n; i++){//因先进入的是根节点，故每层结点多少，队列大小就是多少
                p = temp.front();
                temp.pop();
                row.push_back(p->val);
                    //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(p->left)
                    temp.push(p->left);
                if(p->right)
                    temp.push(p->right);
            }
            if(flag)  //奇数行反转，偶数行不反转
                reverse(row.begin(), row.end());
            res.push_back(row);
        }
        return res;
    }
    
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每个结点访问一次，因为reverse的时间复杂度为$O(n)O(n)$，按每层元素reverse也相当于$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，队列的空间

方法二：双栈法

具体做法：

我们可以利用两个栈遍历这棵二叉树，第一个栈s1从根结点开始记录第一层，然后依次遍历两个栈，遍历第一个栈时遇到的子节点依次加入第二个栈s2中，即是第二层，而遍历第二个栈s2的时候因为是先进后出，因此就是逆序的，再将第二个栈s2的子节点依次加入第一个栈s1中，于是原本的逆序在第一个栈s1中又变回了正序，如果反复交替直到两个栈都空为止。

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        TreeNode* head = pRoot;
        vector<vector<int> > res;
        if(head == NULL)
            return res; //如果是空，则直接返回空vector
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(head); //放入第一次
        while(!s1.empty() || !s2.empty()){ 
            vector<int> temp;
            while(!s1.empty()){ //遍历奇数层
                TreeNode* node = s1.top();
                temp.push_back(node->val); //记录奇数层
                if(node->left)  //奇数层的子结点加入偶数层
                    s2.push(node->left);
                if(node->right) 
                    s2.push(node->right);
                s1.pop();
            }
            if(temp.size()) 
                res.push_back(temp);
            temp.clear();
            while(!s2.empty()){ //遍历偶数层
                TreeNode* node = s2.top();
                temp.push_back(node->val);  //记录偶数层
                if(node->right)  //偶数层的子结点加入奇数层
                    s1.push(node->right);
                if(node->left) 
                    s1.push(node->left);
                s2.pop();
            }
            if(temp.size()) 
                res.push_back(temp);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历二叉树的每个结点
• 空间复杂度：$O(n)O(n)$，两个栈的空间最坏情况为$nn$