把二叉树打印成多行

发表于 更新于 分类于 本文字数： 380 阅读时长 ≈ 1 分钟

JZ78 把二叉树打印成多行

描述

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

例如：

1
给定的二叉树是{1,2,3,#,#,4,5}

imgs

该二叉树多行打印层序遍历的结果是 

1
2
3
4
5
[   
[1],   
[2,3],   
[4,5]   
]

数据范围：二叉树的节点数 $0≤n≤1000$，$0≤val≤1000$

要求：空间复杂度 $O(n)$，时间复杂度 $O(n)$

输入描述：

给定一个二叉树的根节点

示例1

1
2
输入：{1,2,3,#,#,4,5}
返回值：[[1],[2,3],[4,5]]

示例2

1
2
输入：{8,6,10,5,7,9,11}
返回值：[[8],[6,10],[5,7,9,11]]

示例3

1
2
输入：{1,2,3,4,5}
返回值：[[1],[2,3],[4,5]]

示例4

1
2
输入：{}
返回值：[]

题解

初见思路：用队列实现一个$BFS$，然后每一层的都$push_back$进一个$vector$，然后每一层结束后再把这个$vector$给$push_back$到$ans$里面就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> ans;
        
        if(!pRoot) return ans;
        queue<TreeNode*> q;
        TreeNode* curr = pRoot;
        q.push(pRoot);
        while (!q.empty()) {
            int size = q.size();
            vector<int> currLevel;
            for(int i = 0; i < size; i++){
                curr = q.front();
                currLevel.push_back(curr->val);
                q.pop();
                if(curr->left) q.push(curr->left);
                if(curr->right) q.push(curr->right);
            }
            ans.push_back(currLevel);        
        }
        return ans;
    }
};