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


方法一：
bfs层次遍历

思路：
        利用队列实现 bfs 层次遍历。
        重点：计算每一层时，要先记录当前队列的元素个数。（可以实现每层的遍历）
        
        之后，将非空的左儿子节点入队，将非空的右儿子节点入队。
        最后，将偶数层的 vector 反转。

     

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> res;
            vector<int> v;
            if(pRoot==nullptr)
                return res;
            queue<TreeNode*> q;//队列
            q.push(pRoot);//根节点入队
            int id=0;
            while(!q.empty()){
                int num=q.size();//记录当前队列的元素个数
                v.clear();
                id++;
                while(num--){
                    auto t=q.front();//出队
                    q.pop();
                    v.push_back(t->val);
                    if(t->left){//将非空的左儿子节点入队
                        q.push(t->left);
                    }
                    if(t->right){//将非空的右儿子节点入队
                        q.push(t->right);
                    }
                }
                if(id%2==0){//将偶数层反转
                    reverse(v.begin(),v.end());
                }
                res.push_back(v);
            }
            return res;
        }
    
};

时间复杂度：
空间复杂度：


方法二:
dfs 递归

思路：
        重点：记录每个节点的深度，而每一个的深度对应一个 vector。
        因此，可以递归遍历每个节点，记录每个节点的深度。
        最后，将偶数层的vector反转。
 

class Solution {
public:
        vector<vector<int>> res;
        vector<vector<int> > Print(TreeNode* pRoot) {
            dfs(pRoot,1);
            for(int i=1;i<res.size();i+=2){//将偶数层的vector反转
                reverse(res[i].begin(),res[i].end());
            }
            return res;
        }
        
        void dfs(TreeNode* root,int depth){
            if(root==nullptr){
                return;
            }
            if(res.size()<depth){//新建一层
                res.push_back(vector<int>());
            }
            res[depth-1].push_back(root->val);
            dfs(root->left,depth+1);//递归左儿子节点
            dfs(root->right,depth+1);//递归右儿子节点
        }
};


时间复杂度：
空间复杂度：