题目描述
从上到下按层打印二叉树,同一层的结点按从左到右的顺序打印,每一层打印到一行。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4
输出:[[8], [12, 2], [6], [4]]
算法1
(BFS)
1、当树不为空树的时候,让跟节点进入队列
2、构造一个数组,用于收集这一层的所有节点的值,判断当前队列中的数据个数并遍历,将其插入到数组中,再把左右孩子插入其中。
3、将所得到的存储了一层元素数据的数组加入到结果集中。
4、重复动作,直到队列为空。
时间复杂度
O(n)
C++ 代码
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
if(root==NULL) return {}; //当为空树时,返回空数组
vector<vector<int>> res; //结果集数组
queue<TreeNode*> q;
q.push(root); //将树的根节点插入队列
while(!q.empty()){
vector<int> path;
int n=q.size();
//遍历当前队列中的所有节点并存入数组中
for(int i=0;i<n;i++){
TreeNode *temp=q.front();
q.pop();
path.push_back(temp->val);
if(temp->left!=NULL) q.push(temp->left); //将左孩子存入队列
if(temp->right!=NULL) q.push(temp->right); //将右孩子存入队列
}
res.push_back(path);
}
return res;
}