LeetCode-102.题: 二叉树的层序遍历(原创)

【题目描述】

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

【题目链接】. - 力扣(LeetCode)

【解题代码】

package tree.binarytree;import java.util.*;public class LevelOrderTraversal {public static void main(String[] args) {Integer[] array = new Integer[]{1,2,3,4,null,null,5};TreeNode root = TreeNode.constructTree(array);List<List<Integer>> lists = new LevelOrderTraversal().levelOrder(root);lists.forEach(l -> System.out.println(Arrays.toString(l.toArray())));}private List<List<Integer>> levelOrder(TreeNode root) {// 特殊情况处理,如果树根节点为空,返回空列表if (root == null) return new ArrayList<>();// 定义一个队列,临时存放所访问的树节点Queue<TreeNode> queue = new LinkedList<>();// 首先将树的根节点放入队列中queue.add(root);TreeNode node;// 存储所有层节点列表的列表List<List<Integer>> lists = new ArrayList<>();// 初始化当前父节点个数为1(即根节点),以及子节点个数int curLevelCount = 1, nextLevelCount = 0;// 当前层节点列表List<Integer> list = new ArrayList<>();while (curLevelCount > 0) {// 从队列里弹出一个父节点,并将父节点数据减1node = queue.poll();curLevelCount--;// 将此父节点放入当前层节点列表list.add(node.val);// 如果此节点左子节点不为空,放入队列中,并将子节点数目加1if (node.left != null) {queue.add(node.left);nextLevelCount++;}// 如果此节点右子节点不为空,放入队列中,并将子节点数目加1if (node.right != null) {queue.add(node.right);nextLevelCount++;}// 如果当前层父节点访问完毕if (curLevelCount == 0){// 将当前层节点,拷贝到结果列表中,并进行清空lists.add(new ArrayList<>(list));list.clear();// 然后将下一层所有节点作为当前层节点,重启新一轮的遍历curLevelCount = nextLevelCount;nextLevelCount = 0;}}// 最后返回结果return lists;}
}

【解题思路】

        我们之前数据结构学习树遍历的内容,一般都是左、中、右三种遍历循序,按树的层次遍历还没处理过,需要自行思考,不能借鉴教科书了,深入反复思考,得出以下几个要点

  1. 第一层就一个节点,树的根节点,第二层就是根节点的左右子节点,第三层就是根节点的左右子节点的所有左右子节点,后面以此类推。。。
  2. 每次我们可以在队列中保存当前层的树节点,然后一一弹出,放入当前层列表中,并将其子节点放入队列中
  3. 当前层访问结束后,剩下的就是当前层的下一层所有节点。将其设置为新的当前层,反复循环处理即可

按照这个思路,很快就写出算法代码,并提交成功,解题步骤如下:

【解题步骤】

  1. 定义当前层树节点列表以及结果所有层节点列表
    // 定义一个队列,临时存放所访问的树节点
    Queue<TreeNode> queue = new LinkedList<>();
    // 存储所有层节点列表的列表
    List<List<Integer>> lists = new ArrayList<>();
  2. 定义一个队列,临时存放所访问的树节点,首先将树的根节点放入队列中
    // 定义一个队列,临时存放所访问的树节点
    Queue<TreeNode> queue = new LinkedList<>();
    // 存储所有层节点列表的列表
    queue.add(root);
  3. 初始化当前父节点个数为1(即根节点),以及子节点个数
    int curLevelCount = 1, nextLevelCount = 0;
  4. 依次遍历当前层所有节点,一一从队列里弹出,放入当前层节点列表
    while (curLevelCount > 0) {// 从队列里弹出一个父节点,并将父节点数据减1node = queue.poll();curLevelCount--;// 将此父节点放入当前层节点列表list.add(node.val);
  5. 将其左右子节点作为下一层节点加入队列中
    // 如果此节点左子节点不为空,放入队列中,并将子节点数目加1
    if (node.left != null) {queue.add(node.left);nextLevelCount++;
    }
    // 如果此节点右子节点不为空,放入队列中,并将子节点数目加1
    if (node.right != null) {queue.add(node.right);nextLevelCount++;
    }
  6. 如果当前层所有节点遍历完毕,将当前层节点,拷贝到结果列表中,并进行清空,然后将下一层所有节点作为当前层节点,重启新一轮的遍历
    ​
    // 如果当前层父节点访问完毕
    if (curLevelCount == 0){// 将当前层节点,拷贝到结果列表中,并进行清空lists.add(new ArrayList<>(list));list.clear();// 然后将下一层所有节点作为当前层节点,重启新一轮的遍历curLevelCount = nextLevelCount;nextLevelCount = 0;
    }​
  7. 最后返回结果
    return lists;

【思考总结】

  1. 这道理的关键点在于“自顶向下,一层接一层交替访问树节点”;
  2. 算法设计时,可以考虑最简单的情况,试探思考其运行逻辑应该是什么样的
  3. 还是要有精细化的逻辑思维,层次分明,这样在复杂的逻辑也不会乱;
  4. LeetCode解题之前,可以看提示,但一定不要看题解,看了就“破功”了!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/274092.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【ICCV21】Swin Transformer: Hierarchical Vision Transformer using Shifted Windows

文章目录 0. Abstract1. Introduction2. Related Work3. Method3.1 Overall Architecture3.2 Shifted Window based Self-Attention3.3 Architecture Variants 4. Experiments4.1 Image Classification on ImageNet-1K4.2 Object Detection on COCO4.3 Semantic Segmentation o…

文本向量评测MTEB和C-MTEB

文章目录 简介MTEBC-MTEB参考资料 简介 MTEB(Massive Text Embedding Benchmark)是目前评测文本向量很重要的一个参考&#xff0c;其榜单也是各大文本向量模型用来展示与其他向量模型强弱的一个竞技台。 C-MTEB则是专门针对中文文本向量的评测基准。 MTEB MTEB的目的是为了…

OKLink2月安全月报| 2起典型漏洞攻击案例分析

在本月初我们发布的2024年2月安全月报中提到&#xff0c;2月全网累计造成损失约1.03亿美元。其中钓鱼诈骗事件损失占比11.76%。 OKLink提醒大家&#xff0c;在参与Web3项目时&#xff0c;应当仔细调研项目的真实性、可靠性&#xff0c;提升对钓鱼网站和风险项目的甄别能力&…

C语言从入门到熟悉------第二阶段

printf的用法 printf的格式有四种&#xff1a; &#xff08;1&#xff09;printf("字符串\n"); 其中\n表示换行的意思。其中n是“new line”的缩写&#xff0c;即“新的一行”。此外需要注意的是&#xff0c;printf中的双引号和后面的分号必须是在英文输入法下。双引…

portainer管理远程docker和docker-swarm集群

使用前请先安装docker和docker-compose&#xff0c;同时完成docker-swarm集群初始化 一、portainer-ce部署 部署portainer-ce实时管理本机docker&#xff0c;使用docker-compose一键拉起 docker-compose.yml version: 3 services:portainer:container_name: portainer#imag…

[机器视觉]halcon应用实例 找圆

[机器视觉]halcon应用实例 找圆 代码 *清空屏幕&#xff0c;显示控制图像 dev_close_window () dev_update_off () read_image (Image, 形状模板图) dev_open_window_fit_image (Image, 0, 0, -1, -1, WindowHandle) dev_display (Image) *创建测量模型 create_metrology_mod…

AD20新建工程步骤

1 新建工程 2 创建 3 新建原理图 4 新建PCB图 5 对原理图贺PCB都进行保存 6 新建原理图库贺PCB库&#xff0c;以及保存 最后在保存位置上都可以看到 打开的时候直接打开工程&#xff0c;它自己就会把这些链接在一起

UVa11595 Crossing Streets EXTREME

题目链接 UVa11595 - Crossing Streets EXTREME 题意 平面上有 n&#xff08;n≤35&#xff09;条直线&#xff0c;各代表一条街道。街道相互交叉&#xff0c;形成一些路段&#xff08;对应于几何上的线段&#xff09;。你的任务是设计一条从A到B的路线&#xff0c;使得穿过路…

c++: 引用能否替代指针? 详解引用与指针的区别.

文章目录 前言1. 引用和指针的最大区别:引用不能改变指向2. 引用和指针在底层上面是一样的3. 引用和指针在sizeof面前大小不同4. 有多级指针,没有多级引用5.引用是引用的实体,指针会向后偏移同一个类型的大小 总结 前言 新来的小伙伴如果不知道引用是什么?可以看我的上一篇文…

AI新工具(20240312) Midjourney官方发布角色一致性功能;免费且开源的简历制作工具;精确克隆语调、控制声音风格

1: Midjourney角色一致性功能 使人物画像在多方面高度一致成为可能。 Midjourney的角色一致性功能的使用方法如下&#xff1a; ⭐在你的输入指令后面加上 --cref URL&#xff0c;其中URL是你选择的角色图像的链接。 ⭐你可以通过 --cw 参数来调整参照的强度&#xff0c;范围…

spring boot 使用 webservice

spring boot 使用 webservice 使用 java 自带的 jax-ws 依赖 如果是jdk1.8,不需要引入任何依赖&#xff0c;如果大于1.8 <dependency><groupId>javax.jws</groupId><artifactId>javax.jws-api</artifactId><version>1.1</version&g…

【Linux】文件缓冲区|理解文件系统

目录 预备知识 观察现象 第一&#xff1a;携带\n&#xff0c;不使用fork()&#xff0c;打印到显示器 第二&#xff1a;携带\n&#xff0c;使用fork()&#xff0c;打印到显示器 第三&#xff1a;携带\n&#xff0c;使用fork()&#xff0c;打印到文件里 第四&#xff1a;不携…

案例分析篇03:一篇文章搞定软考设计模式考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)

专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…

IPSec NAT穿越原理

一、IPSec VPN在NAT场景中存在的问题 当某些组网中&#xff0c;有的分支连动态的公网IP地址也没有&#xff0c;只能由网络中的NAT设备进行地址转换&#xff0c;才能访问互联网&#xff0c;然而IPsec是用来保护报文不被修改的&#xff0c;而NAT需要修改报文的IP地址&#xff0c…

十大排序算法(冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序)

目录 一、冒泡排序&#xff1a; 二、插入排序&#xff1a; 三、选择排序&#xff1a; 四、希尔排序&#xff1a; 五、堆排序&#xff1a; 六、快速排序&#xff1a; 6.1挖坑法&#xff1a; 6.2左右指针法 6.3前后指针法&#xff1a; 七、归并排序&#xff1a; 八、桶…

力扣hot100:240.搜索二维矩阵II(脑子)

吉大21级算法分析与设计的一道大题&#xff0c;由于每一行都是排好序的直接逐行二分 可以达到&#xff1a;O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分&#xff1a; 在矩阵中用中心点比较&#xff0c;如果target大于中心点的值&#xff0c;则由于升序排列&am…

vue学习笔记23-组件事件⭐

组件事件 在组件的模板表达式中&#xff0c;可以直接使用$emit方法触发自定义事件&#xff1b;触发自定义事件的目的是组件之间传递数据 好好好今天又碰到问题了&#xff0c;来吧来吧 测试发现其他项目都可以 正常的run ,就它不行 搜索发现新建项目并进入以后&#xff0c;用指…

C语言--- 指针运算笔试题详解

目录 题目1&#xff1a; 题目2&#xff1a; 题目3&#xff1a; 题目4&#xff1a; 题目5&#xff1a; 题目6&#xff1a; 题目7&#xff1a; 题目1&#xff1a; #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int *ptr (int *)(&a 1);print…

新书推荐|职业教育赛教一体化课程改革系列教材之spark大数据分析

由武汉唯众智创科技有限公司统一规划并参与编写的“职业教育赛教一体化课程改革系列教材”-《spark大数据分析》正式出版上线&#xff0c;(其它八本为《云计算技术与应用》《大数据技术与应用Ⅰ》《网络综合布线》《物联网.NET开发》《物联网嵌入式开发》《物联网移动应用开发》…

Cloud-Eureka服务治理-Ribbon负载均衡

构建Cloud父工程 父工程只做依赖版本管理 不引入依赖 pom.xml <packaging>pom</packaging><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.9.RELEA…