下面以一道力扣题为例:
代码和解释如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//要求:返回一个结果集,创建一个存储集合的集合;
List<List<Integer>> res = new ArrayList<List<Integer>>();
//基本思路:整个过程借助队列实现:(队列是一个接口,需要一个实现类)
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return res;
}
//root不为空,直接添加入队列;
queue.offer(root);
//创建一个死循环,当队列为空,即遍历结束时退出;
while(true){
//具体描述:
//1.创建一个可更新的集合,记录每层的结果;
//2.定义一个变量记住每层的元素数量,方便控制队列的弹出的个数;
//由于要先把前一层的元素全部弹出,所以队列中是下一层要处理的元素;
List<Integer> list = new ArrayList<>();
int size = queue.size();
//根据处理个数,用for循环多次处理;
for(int i = 0;i<size;i++){
//1.先弹出元素,存入该元素的值
//2.弹出一个元素,就添加其两边的左右节点,因此需要先记住结点
TreeNode curNode = queue.poll();
list.add(curNode.val);
if(curNode.left != null){
queue.offer(curNode.left);
}
if(curNode.right != null){
queue.offer(curNode.right);
}
}
//整个for循环完成了对本层数据的遍历并存入了一个临时集合,最后把集合收集到结果集
res.add(list);
if(queue.isEmpty()){
break;
}
}
return res;
}
}
离开这一道题,我们应该明白什么?
层序遍历主要是如何实现的?依赖于什么数据结构,核心的想法是什么?
层序遍历的实现:
1.依赖于队列的数据结构
2.核心怎么实现:
1)创建一个队列的容器对象。
2)判断根节点是否为空,不为空则添加根节点到队列中。
3)遍历是一个循环性的工作,写一个死循环,死循环的第一步就是跳出死循环的条件:当队列中没有东西时退出(换句话说,没东西可遍历了)。
4)每弹出一个元素,再访问(就是进行符合场景的操作),最后添加两边的左右子节点(如果不为空的话)。