树的层序遍历(详解)

devtools/2024/12/5 12:46:10/

下面以一道力扣题为例:

代码和解释如下:

java">/*** 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)每弹出一个元素,再访问(就是进行符合场景的操作),最后添加两边的左右子节点(如果不为空的话)。


http://www.ppmy.cn/devtools/23856.html

相关文章

123.Mit6.S081-实验1-Xv6 and Unix utilities

今天我们来进行Mit6.S081实验一的内容。 实验任务 一、启动xv6(难度&#xff1a;Easy) 获取实验室的xv6源代码并切换到util分支。 $ git clone git://g.csail.mit.edu/xv6-labs-2020 Cloning into xv6-labs-2020... ... $ cd xv6-labs-2020 $ git checkout util Branch util …

成电少年学fpga培训就业班怎么样

成电少年学是专注做FPGA培训的&#xff0c;以就业为导向&#xff0c;学习FPGA还是很有前途的&#xff0c;如果你是像电气、通信、自动化、物联网、集成电路这类专业&#xff0c;又不是名校高学历的&#xff0c;确实有必要可以考虑下校外培训机构。找工作多少会遇到一些问题&…

c# 构造函数 静态构造函数 内联字段(即静态字段和实例字段) 父类构造函数 父类静态构造函数 父类内联字段 执行顺序

顺序如下&#xff1a; 1.子类的内联字段 2.子类的静态构造函数 3.父类的内联字段 4.父类的静态构造函数 5.父类的构造函数 6.子类的构造函数 7.子类的方法 public class A{public static string a1"A0";static A(){Console.WriteLine("父类内联字段&#xff1a;…

springboot拦载器

1、拦载器 package com.Interceptor;import com.alibaba.fastjson.JSON; import com.alibaba.fastjson.JSONObject; import org.springframework.web.servlet.HandlerInterceptor; import org.springframework.web.servlet.ModelAndView;import javax.security.auth.login.Log…

DOS比较运算符及常用操作

目录 rem 比较运算符:事例批处理 数值计算与大小比较注释比较大小if语句while循环输出到屏幕输出到文本读取文本到剪切板删除文件暂停关闭回显 rem 比较运算符: EQU - 等于 NEQ - 不等于 LSS - 小于 LEQ - 小于或等于 GTR - 大于 GEQ - 大于或等于 例如 if not %in%2 goto 2 如…

M2 Mac mini跑Llama3

前言 在4-19左右&#xff0c;Meta 宣布正式推出下一代开源大语言模型 Llama 3&#xff1b;共包括 80 亿和 700 亿参数两种版本&#xff0c;号称 “是 Llama 2 的重大飞跃”&#xff0c;并为这些规模的 LLM 确立了新的标准。实际上笔者早就体验过&#xff0c;只不过自己电脑没什…

Redisson分布式锁

目录 Redisson的基本使用 Redisson的基本原理 Redis中的使用 简单了解一下Lua脚本 加锁脚本 解锁脚本 看门口续期lua脚本 源码 tryLock方法 tryAcquireAsync方法 unlock方法 renewExpiration&#xff08;&#xff09;方法 在一个进程的各个线程间保持数据的同步可以…

navicat连接postgresql报错解决方案

navicat连接postgresql报错解决方案 问题描述原因分析&#xff1a;解决方案&#xff1a;1、将navicat升级到16.2以上版本2、降级pgsql3、修改dll配置文件 问题描述 使用Navicat连接postgresql时&#xff0c;出现如下错误。 原因分析&#xff1a; 由于pgsql 15版本以后&#…