[编程题] 知识点: 广度优先遍历-二叉树的层序遍历
题目
练习:二叉树的层序打印(使用BFS)
题目
输入输出
Java代码
提示:
对于题目中方法是要求一开始返回一个int数组的,但是我们事先不知道树的节点的个数,如果我们遍历统计树的节点个数,显然是不划算的。
那么我们如何new 这个数组的长度呢? 因为数组new 不像集合,数组是要指定初始大小的、
所以我们采用先放入一个集合的list中,处理完了之后再从集合获取集合的使用大小,把其中元素转入到int数组中。
- 这里依然碰到一个问题,如果正常返回,那么返回一个带有实际元素的数组
- 但是如果树为空,我们如何返回一个empty的数组呢。如果用new int[1];默认是被初始化为[0]的还是不满足[]
解决:
使用stream直接把list转为int[] 返回。省去了好多代码。也可以返回空的数组。
如果是空的集合,那么返回空的数组;
如果是非空集合,转换为数组返回:
return lis.stream().mapToInt(Integer::valueOf).toArray();
Java代码:
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/*思想:相当于树的广度优先遍历:需要借助队列*/
public int[] levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();//队列
//由于不知道树的元素个数,就先放入list,最终根据list生成一个int[]返回
ArrayList<Integer> lis = new ArrayList<>();
queue.offer(root);//把root节点放入到队列
//极端条件判断(当我们要返回一个空数组的话,new int[1]是默认为[1]的数组的;故用如下返回[])
if(root==null) {return lis.stream().mapToInt(Integer::valueOf).toArray();}
//当队不为空的时候执行
while(!queue.isEmpty()){
TreeNode node = queue.poll();
lis.add(node.val);//放入到结果集
//判断左节点是否空,不为空就访问并且加入队列中
if(node.left==null && node.right==null) {continue;}
if(node.left!=null){
queue.offer(node.left);
}
//同理,右节点
if(node.right != null){
queue.offer(node.right);
}
}
//退出while后就可以返回结果了(建议通过如下的stream方式直接返回)
//int[] res = new int[lis.size()];
//for(int i=0;i<lis.size();i++){res[i] = lis.get(i);}
return lis.stream().mapToInt(Integer::valueOf).toArray();
}
}