思路

题目要求我们将同一层按照从左到右的顺序进行合并整理成输出，我们将题目解读并翻译为层序遍历问题

• 通过层序遍历的方式进行顺序访问
• 维护一个队列结构，队列可以帮助我们实现先进先出，因此只要层序访问入队出队即可

方法一：非递归层序遍历

具体做法 首先处理特殊情况，比如指针为空的情况，直接返回空结果[] 维护一个队列，其中存储的信息是当前层的结点指针，队列一直在第二个while循环内重复的工作就是出队当前队首结点，同时将其左右子节点入队。 在层与层之间，通过第二次while循环之前的当前队列容量大小来控制层之间的间隔。 层序遍历进行每一层的结点添加统计

以下为c++代码展示

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            if(pRoot==NULL) return {};                // 指针为空的情况处理
            vector<vector<int>> res;
            queue<TreeNode*> q;                       // 采用队列非递归的方式进行层序遍历
            TreeNode* p = pRoot;
            q.push(p);                                // 首先将根节点入队
            while(!q.empty()) {                       // 判断当前层是否为空
                vector<int> level;
                int n = q.size();                     // 获取当前层内的结点数量
                while(n){                             // 对当前层内每一个结点进行左右子树的访问
                    TreeNode* a = q.front();          // 队首按序出列即当前层的vector内容
                    if(a->left) q.push(a->left);      // 左孩子入队
                    if(a->right)q.push(a->right);     // 右孩子入队
                    q.pop();                          // 当前层的结点指针出队
                    level.push_back(a->val);          // 将当前层结点记录到本层的vector中
                    n--;
                }
                res.push_back(level);                 // 收集每一层的vector整合为最终结果
            }
            return res;
        }
    
};

复杂度分析

• 时间复杂度：O(N)，每个节点进出队列一次
• 空间复杂度：O(N)，使用了树状结构相当结点的空间，虽然小于N但是也是N的量级的

方法二：前序遍历记录深度

我们通过传统的前序遍历的方式，通过记录深度来判定结点对应的值应该加入到哪一个序列中

class Solution {
public:
        vector<vector<int>> res;
        void preOrder(TreeNode* root,int deep) {
            if(!root) return;                            // 如果当前结点为空则直接返回
            if(deep > res.size()) res.push_back({});     // 达到一个深度级就会在res中增加一个空序列
            res[deep-1].push_back(root->val);            // 在res中对应深度的序列中添加元素
            preOrder(root->left,deep+1);                 // 递归左子树，并深度+1
            preOrder(root->right, deep+1);               // 递归右子树，并深度+1
        }
        vector<vector<int> > Print(TreeNode* pRoot) {
            preOrder(pRoot,1);                           // 前序遍历，保证同一层内的访问顺序是从左到右的
            return res;
        }
};

复杂度分析

• 时间复杂度：O(N)，每个节点进出队列一次
• 空间复杂度：O(N)，维护递归的栈空间