题目信息
时间： 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 List<List<Integer>> levelOrder(TreeNode root) {
//当根节点为空，则返回空列表 []
if(root == null){
return new ArrayList<>(0);
}
//打印结果列表 res = []
List<List<Integer>> res = new ArrayList<>();
//包含根节点的队列 queue = [root]
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//BFS 循环： 当队列 queue 为空时跳出
while(!queue.isEmpty()){
//新建一个临时列表 ans ，用于存储当前层打印结果
List<Integer> ans = new ArrayList<>();
//当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）；
for(int i = queue.size(); i > 0; i--){
//出队： 队首元素出队，记为 t
TreeNode t = queue.poll();
//打印： 将 t.val 添加至 ans 尾部
ans.add(t.val);
//添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue
if(t.left != null){
queue.add(t.left);
}
if(t.right != null){
queue.add(t.right);
}
}
//将当前层结果 tmp 添加入 res
res.add(ans);
}
//返回打印结果列表 res 即可
return res;
}
}
复杂度分析：
- 时间复杂度 O(N) ：N 为二叉树的节点数量，即 BFS 需循环 N 次。
- 空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 队列queue 中，使用 O(N) 大小的额外空间。
其他优秀解答
一般在树相关的题目中都可以考虑递归解法
class Solution {
//输出结果列表res ，用于存储所有层的列表
List<List<Integer>> res = new ArrayList();
public List<List<Integer>> levelOrder(TreeNode root){
//递归调用函数，从第0层开始
recur(root,0);
return res;
}
public void recur(TreeNode root,int k){
if(root != null){
//如果列表层数小于二叉树的层数，新增当前层的列表
if(res.size() <= k){
res.add(new ArrayList());
}
//将当前层的元素添加到当前层列表中
res.get(k).add(root.val);
//递归调用二叉树的左子树，层数+1
recur(root.left,k+1);
//递归调用二叉树的右子树，层数+1
recur(root.right,k+1);
}
}
}