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

题目的主要信息：

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

方法一：

层次遍历。用队列进行层次遍历，首先将根结点入队。通过一个循环，当队列不为空时，将队列中的元素逐个出列记录在ans中，同时每出列一个结点，就把该结点的左右孩子入列（如果有的话），这样能保证按照层次对树进行遍历。 具体做法：

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);//根结点入列
        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);//右孩子入列
            }
            res.push_back(ans);
        }
        return res;
    }
    
};

复杂度分析：

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

方法二：

采用递归。用ans保存每一层的值，depth记录当前递归的深度，从第一层开始递归。如果root为NULL表示递归结束。每递归到新的一层，且该层没有访问过，就创建当层行的向量，将root的值放入本层的行向量中，然后深度加一，向左右孩子递归。

具体做法：

class Solution {
public:
    vector<vector<int>> ans;//保存每一行的值
    void LevelTraversal(TreeNode* root,int depth) {
        if(root==NULL){
            return;
        }
        if(ans.size() < depth){//递归到新一层
            ans.push_back(vector<int>{});//创建当层行的向量
        }
        ans[depth - 1].push_back(root->val); //将root的值放入本层向量中
        //向左右孩子递归
        LevelTraversal(root->left, depth + 1);
        LevelTraversal(root->right, depth + 1);
    }
    
    vector<vector<int> > Print(TreeNode* pRoot) {
        LevelTraversal(pRoot,1); //从第1层开始递归
        return ans;
     }
};

复杂度分析：

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