题目信息
时间： 2019-06-25
题目链接：Leetcode
tag：BFS（广度优先搜索） 队列
难易程度：中等
题目描述：
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
示例1:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：[3,9,20,15,7]
1.节点数量 <= 1000
解题思路
二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。
BFS 通常借助 队列 的先入先出特性来实现。
代码
class Solution {
public int[] levelOrder(TreeNode root) {
//当树的根节点为空，则直接返回空列表 []
if(root == null){
return new int[0];
}
//包含根节点的队列 queue = [root]
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//包含答案的ans列表
List<Integer> ans = new ArrayList<>();
//BFS 循环： 当队列 queue 为空时跳出
while(!queue.isEmpty()){
//出队： 队首元素出队，记为 t；
TreeNode t = queue.poll();
//打印： 将 t.val 添加至列表 ans 尾部；
ans.add(t.val);
//添加子节点： 若t的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
if(t.left != null){
queue.add(t.left);
}
if(t.right != null){
queue.add(t.right);
}
}
//打印结果数组 res = []
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++){
res[i] = ans.get(i);
}
//返回打印结果数组 res
return res;
}
}
复杂度分析：
- 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
- 空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue中，使用 O(N) 大小的额外空间。
其他优秀解答
一般在树相关的题目中都可以考虑递归解法
class Solution {
//新建一个临时列表 level ，用于存储所有层的列表
List<List<Integer>> level = new ArrayList();
//打印答案列表 res = []
List<Integer> ans = new ArrayList<>();
public int[] levelOrder(TreeNode root) {
if(root == null){
return new int[0];
}
//递归调用函数，从第0层开始
recur(root,0);
//遍历每层的列表
for(List<Integer> levels : level){
//遍历每层的元素
for(Integer x : levels){
//将元素添加到答案列表res中
ans.add(x);
}
}
//打印结果数组 res = []
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++){
res[i] = ans.get(i);
}
return res;
}
public void recur(TreeNode root,int k){
if(root != null){
//如果列表层数小于二叉树的层数，新增当前层的列表
if(level.size() <= k){
level.add(new ArrayList());
}
//将当前层的元素添加到当前层列表中
level.get(k).add(root.val);
//递归调用二叉树的左子树，层数+1
recur(root.left,k+1);
//递归调用二叉树的右子树，层数+1
recur(root.right,k+1);
}
}
}