题目主要信息：

将一棵n个节点的二叉树按照从上到下按层的方式打印，每层按照从左到右的顺序输出。

思路：

题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：

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

综上，反过来，每次只要在队列长度内循环，必定是一层，一层访问完毕再更新队列长度即可。

方法一：非递归层次遍历

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;
            while(!temp.empty()){
                vector<int> row;  //记录二叉树的某一行
                int n = temp.size();
                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);
                }
                res.push_back(row);
            }
            return res;
        }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每个结点访问一次
• 空间复杂度：$O(n)O(n)$，队列的空间

方法二：递归层次遍历

具体方法：

除了用队列非递归可以实现二叉树的层次遍历，使用递归也可以，只是需要在函数加入记录深度的遍历，每往下一层深度加1，同时保存结果的vector正好对应每层一个数组，因此vector的大小正好是遍历的深度，由此可以实现递归。

class Solution {
public:
    void traverse(TreeNode* root, vector<vector<int>>& ans, int depth) {
        if(root) {
            if(ans.size() < depth)             //新的一层
                ans.push_back(vector<int>{});  
            //vector从0开始计数因此减1，在节点当前层的vector中插入节点
            ans[depth - 1].push_back(root->val); 
        }
        else
            return;
        traverse(root->left, ans, depth + 1); //递归左右时结点记得加1
        traverse(root->right, ans, depth + 1);
    }
    vector<vector<int> > Print(TreeNode* pRoot) {//层次遍历
        vector<vector<int>> ans;
        traverse(pRoot, ans, 1); //树的层级从1开始递归计数
        return ans;
     }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每个结点访问一次
• 空间复杂度：$O(n)O(n)$，递归栈的最大深度