题解 | #把二叉树打印成多行#

题意思路：
从上到下按层打印二叉树，同一层结点从左至右输出,每一层输出一行。
也就是对二叉树做一遍层次遍历

方法一:使用队列模拟二叉树的层次遍历

二叉树的层次遍历 ，顾名思义就是指从二叉树的第一层（根结点）开始，

从上至下逐层遍历，在同一层中，则按照从左到右的顺序对结点逐个访问。

1)先将根结点加入队列，然后将当前队列中的所有结点遍历，这时队列中的所有结点都是同一层，将遍历结果加入答案，将遍历后结点加入队列。

2）然后不断枚举每个结点的子树，直至完成逐层的层次遍历。

复杂度分析

时间复杂度：O()，表示二叉树结点数量，层次遍历所有结点。

空间复杂度：O()，队列存放每一层结点答案

图文详解：

/*
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)
    {
        vector<vector<int>> res;
        if (!pRoot)return res;         //特判根结点为空时
        queue<TreeNode *> q; //新建队列用来模拟二叉树的层次遍历
        q.push(pRoot);         //先将二叉树的根结点加入队列中
        while (q.size())
        {
            vector<int> now; //存放每一层的结点
            int cnt = q.size();
            while (cnt--)
            {                        //将当前层结点一次性枚举完
                auto p = q.front(); //取出队头
                q.pop();
                now.push_back(p->val);
                if (p->left)q.push(p->left); //如果当前结点有左右子树
                if (p->right)q.push(p->right); //则加入队列下一层枚举
            }
            res.push_back(now); //得到每一层的遍历结果
        }
        return res;
    }
};

方法二：递归枚举
通过深度优先的遍历顺序，记录当前结点的深度，判断是否加入每层的遍历结果
深度优先搜索是先序遍历的推广，深度优先搜索的非递归实现使用了一个栈，这里可以使用递归模拟栈。

复杂度分析

时间复杂度：O()，表示二叉树结点数量，递归遍历所有结点。

空间复杂度：O()，存储结果的必要数组不算开辟额外空间

/*
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>> res;
    void preOrder(TreeNode *root, int deep)
    {
        if (!root)return; //如果当前结点为空则返回
        if (res.size() == deep)res.push_back({});            //如果当前层等于当前深度 加入层
        res[deep].push_back(root->val); //将当前结点的值加入当前深度那一层中
        if (root->left)preOrder(root->left, deep + 1); //如果左右子树有值则递归枚举
        if (root->right)preOrder(root->right, deep + 1);
    }
    vector<vector<int>> Print(TreeNode *pRoot)
    {
        if (!pRoot)return res;
        preOrder(pRoot, 0); //当前为第0层 加入根结点dfs
        return res;
    }
};