题目的主要信息：

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）。

方法一：

层次遍历。用队列进行层次遍历，首先将根结点入队。通过一个循环，当队列不为空时，将队列中的元素逐个出列记录在ans中，同时每出列一个结点，就把该结点的左右孩子入列（如果有的话），这样能保证按照层次对树进行遍历，但是题目要求的是按照之字形顺序打印，实际上就是在偶数层翻转一下，因此用level记录层次，每当到达偶数层就翻转该层的结点。

具体做法：

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;//保存遍历结果
        if (pRoot==NULL){//如果根为NULL
            return res;
        }
        queue<TreeNode*> q;
        q.push(pRoot);//根结点入列
        int level = 0;//层
        while (!q.empty()) {//层次遍历
            int len = q.size();
            vector<int> ans;//每一层的
            for(int i = 0;i < len; i++) {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);
                if (node->left) q.push(node->left);//左孩子入列
                if (node->right) q.push(node->right);//右孩子入列
            }
            level++;
            if (level%2==0){ //偶数层是从右往左遍历
                reverse(ans.begin(), ans.end());//将该层的值翻转
            }
            res.push_back(ans);
        }
        return res;
    }
    
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历一遍整个树。
• 空间复杂度：$O(n)O(n)$，队列大小为n。

方法二：

双栈法。首先明确栈的性质，存入栈中的顺序与从栈中输出的顺序相反。我们可以利用栈的这个性质进行交叉叫顺打印，用stack1保存奇数层的结点，stack2保存偶数层的结点。先把根结点放入stack1中，如果当前stack1不为空，说明当前层是奇数层，逐个输出栈顶元素，将输出结点的子女按照从左到右的顺序存入stack2中，这样能保证到达偶数层时，stack2中的出栈顺序为从右往左；当前层是偶数层，逐个输出栈顶元素，将输出结点的子女按照从右往左的顺序存入stack1中，这样能保证到达奇数层时，stack1中的出栈顺序为从左往右。将每层元素存入result中，最后返回result。 具体做法：

class Solution{
public:
    vector<vector<int> > Print( TreeNode* pRoot){
        vector<vector<int> > result;
        if(pRoot==NULL){//根结点为NULL，返回空
            return result;
        }
        stack<TreeNode*> stack1, stack2;
        stack1.push(pRoot);//放入根结点
        while(!stack1.empty() || !stack2.empty() ){
            vector<int> ret1,ret2;
            TreeNode* cur = NULL;
            while( !stack1.empty()){//奇数层
                cur = stack1.top();
                //从左往右存子女到stack2中，stack2中出栈将以从右往左的顺序
                if(cur->left) stack2.push(cur->left);
                if(cur->right) stack2.push(cur->right);
                ret1.push_back(stack1.top()->val);//保存本层所有结点值
                stack1.pop();
            }
            if(ret1.size()) result.push_back(ret1);
            while( !stack2.empty()){//偶数层
                cur = stack2.top();
                 //从右往左存子女到stack1中，stack1中出栈将以从左往右的顺序
                if(cur->right) stack1.push( cur->right);
                if(cur->left) stack1.push( cur->left);
                ret2.push_back(stack2.top()->val); //保存本层所有结点值
                stack2.pop();
            }
            if(ret2.size()) result.push_back(ret2);
        }
        return result;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历一遍整个树。
• 空间复杂度：$O(n)O(n)$，栈大小为n。