当前位置: 首页 > news >正文

【C++】102.二叉树的层序遍历

题目描述

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

示例1:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

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

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000

思路分析

这个问题实际上可以只用一个队列就实现,只需要再增加一个变量levelSize,用来记录每一层的数据个数,然后再让这个队列一层一层的出去。之前的方法中,实际上队列并不是一层一层出去的,它有可能队列里面同时有两层的数据,我们以下面这个图来解释一下原因:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

如果有两层队列实现的话,3这个节点出来的时候,会让920这两个节点进入队列,而9这个节点出来的时候会让15这个节点进入队列,这个时候队列里面就同时有了第2层和第3层的数据。

所以我们想通过levelSize来达到一个目的:控制这个队列实现一层一层的出去。

那我们要怎么实现呢?我们仍然以刚才的图来进行分析:

3节点进入队列的时候,它的层数为1,由于它是根节点,所以它肯定只有一个,所以3就可以直接出队列。这个时候我们让levelSize进行自减操作它就变成了0,表示这一层已经出完了。

那么由于3节点出的时候会把920也带进来,也就是说当前层的节点全部出队列的时候一定是下一层的节点全部进入队列,这个时候我们将levelSize重新更新为第二层节点的数目也就是2,然后再进行出队列的操作:9节点出队列同时将15节点带进队列,然后levelSize自减变为120节点出队列同时将15节点和7节点带进队列,levelSize再自减变为0。这个时候就说明第二层也出完了。那么此时第三层都在队列里面所以我们再次更新levelSize的值为3,依次类推直到整棵树都被遍历完就实现了只用一个队列实现层序遍历。

那么根据以上的思路,我们就可以写出下面的代码:

完整代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;int levelSize = 0;if (root)//如果根不为空,就入队列{q.push(root);levelSize = 1;}vector<vector<int>> vv;//用来存放一层一层出的节点while (!q.empty())//如果队列不等于空,就说明树还没有被遍历完{//通过levelSize控制一层一层出vector<int> v;//用来存放每一层的数据while (levelSize--)//levelSize是几循环就执行几次,--levelSize表示的则是执行(levelSize - 1)次{TreeNode* front = q.front();//先取队头的数据q.pop();v.push_back(front->val);//进去的同时把该节点的下一层往队列里面带if (front->left)//左如果不为空就让左入队列q.push(front->left);if (front->right)//右如果不为空就让右入队列q.push(front->right);}//走到这里就说明当前层已经出完了,就把当前层所出的数据放到vv里面vv.push_back(v);//更新下一层的数据levelSize = q.size();}return vv;}
};

运行结果
在这里插入图片描述

相关文章:

【C++】102.二叉树的层序遍历

题目描述 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]]示例 2&#xff1…...

Java学习笔记006——子类与父类的类型转换

在Java中&#xff0c;类型转换主要涉及到两种类型&#xff1a;向上类型转换&#xff08;Upcasting&#xff09;和向下类型转换&#xff08;Downcasting&#xff09;。 1. 向上类型转换&#xff08;Upcasting&#xff09;&#xff1a; 向上类型转换是将子类的对象转换为父类类…...

FedAsync Asynchronous Federated Optimization

文章目录 IntroductionMethodologyConvergence analysisExperiments Introduction 联邦学习有三个关键属性: 不频繁的任务激活。对于弱边缘设备&#xff0c;学习任务只在设备空闲、充电、连接非计量网络时执行.沟通不频繁。边缘设备和远程服务器之间的连接可能经常不可用、缓…...

学习基于 JavaScript 语言 的计算机界三大神书”之一 ——SICP

如何阅读“计算机界三大神书”之一 ——SICP 《计算机程序的构造和解释》&#xff08;Structure and Interpretation of Computer Programs&#xff0c;简记为SICP&#xff09;是MIT的基础课教材&#xff0c;出版后引起计算机教育界的广泛关注&#xff0c;对推动全世界大学计算…...

【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(一)-向量扩展编程模型

1. 引言 以下是《riscv-v-spec-1.0.pdf》文档的关键内容&#xff1a; 这是一份关于向量扩展的详细技术文档&#xff0c;内容覆盖了向量指令集的多个关键方面&#xff0c;如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量…...

K8s 镜像缓存管理 kube-fledged 认知

写在前面 博文内容为K8s 镜像缓存管理 kube-fledged 认知内容涉及&#xff1a; kube-fledged 简单介绍部署以及基本使用 理解不足小伙伴帮忙指正 不必太纠结于当下&#xff0c;也不必太忧虑未来&#xff0c;当你经历过一些事情的时候&#xff0c;眼前的风景已经和从前不一样了。…...

ModbusTcp协议

Modbus TCP是一种通信协议&#xff0c;用于工业设备之间的通信。它是Modbus协议家族中的一个成员&#xff0c;最初是为串行通信设计的&#xff0c;但后来扩展到了TCP/IP网络。Modbus TCP/IP是一种公开的标准&#xff0c;由Modbus组织制定&#xff0c;并且被广泛应用于工业自动化…...

常用工具——Gradle

前言 实践是最好的学习方式&#xff0c;技术也如此。 文章目录 前言一、Gradle 简介二、文件结构详解 一、Gradle 简介 Gradle 文件是一个独立于 android 之外的一个东西&#xff1b; 是什么 gradle 就是编译、打包 Android 工程的一个构建工具&#xff1b;build.gradle 文件&…...

OpenHarmony教程指南—Navigation开发 页面切换场景范例

简介 在应用开发时&#xff0c;我们常常遇到&#xff0c;需要在应用内多页面跳转场景时中使用Navigation导航组件做统一的页面跳转管理&#xff0c;它提供了一系列属性方法来设置页面的标题栏、工具栏以及菜单栏的各种展示样式。除此之外还拥有动态加载&#xff0c;navPathSta…...

2024-简单点-picamera2除了文档还有哪里可以学习实例?

picamera2学习例子 去github的picamera2库&#xff0c;找app和examples目录&#xff0c;然后学习...

JavaScript实现点击鼠标弹钢琴的效果

思路&#xff1a; 图片设置宽900px&#xff0c;找到鼠标按下时的x坐标和img距离body的x坐标&#xff0c;两个值相减&#xff0c;然后除100取整&#xff0c;赋值给a&#xff0c;通过判断a的值来确定放出那个音乐。 完整代码&#xff1a; <!DOCTYPE html> <html lan…...

docker-compose Install rustdesk

RustDesk RustDesk 是一款开源的远程支持和远程桌面工具,它旨在为用户提供便捷的远程协助和远程访问功能。 默认情况下,hbbs 监听21115(tcp), 21116(tcp/udp), 21118(tcp),hbbr 监听21117(tcp), 21119(tcp)。务必在防火墙开启这几个端口, 请注意21116同时要开启TCP和UDP。…...

初学C++

注释 变量 作用&#xff1a;给一段指定的内存空间起名&#xff0c;方便操作这段内容 数据类型 变量名 变量初始值; 常量 用于记录程序中不可更改的数据 宏常量&#xff1a; #define 宏常量 常量值 const修饰的变量&#xff1a; const 数据类型 常量名 常量值; 关键字 …...

数据分析-Pandas数据y轴双坐标设置

数据分析-Pandas数据y轴双坐标设置 数据分析和处理中&#xff0c;难免会遇到各种数据&#xff0c;那么数据呈现怎样的规律呢&#xff1f;不管金融数据&#xff0c;风控数据&#xff0c;营销数据等等&#xff0c;莫不如此。如何通过图示展示数据的规律&#xff1f; 数据表&…...

Android多线程实现方式及并发与同步,Android面试题汇总

一. 开发背景 想要成为一名优秀的Android开发&#xff0c;你需要一份完备的知识体系&#xff0c;在这里&#xff0c;让我们一起成长为自己所想的那样。 我们的项目需要开发一款智能硬件。它由 Web 后台发送指令到一款桌面端应用程序&#xff0c;再由桌面程序来控制不同的硬件设…...

2023年全国职业院校技能大赛中职组大数据应用与服务赛项题库参考答案陆续更新中,敬请期待…

2023年全国职业院校技能大赛中职组大数据应用与服务赛项题库参考答案陆续更新中&#xff0c;敬请期待… 武汉唯众智创科技有限公司 2024 年 2 月 联系人&#xff1a;辜渝傧13037102709 题号&#xff1a;试题01 模块三&#xff1a;业务分析与可视化 &#xff08;一&#xff0…...

设计MySQL数据表的几个注意点

最近合作搞项目&#xff0c;发现了很多问题。特别的&#xff0c;数据库层面上的问题更为致命。记录一下&#xff0c;希望后面看到博客的同学们注意。 注意&#xff1a;以下观点只用于一般情况下的单体、微服务&#xff0c;不保证适用所有场景。 一、ID问题 ID名称问题 如下图…...

android 键盘遮挡输入框问题回忆

背景 刚开始做Android的时候&#xff0c;有一次遇到输入框位于页面底部&#xff0c;弹出的键盘老是遮挡输入框&#xff0c;这就给人一种感觉----不咋舒服。当时&#xff0c;网上百度了一遍&#xff0c;后面终于解决了&#xff0c;由于当时天天加班&#xff0c;没时间写博客&…...

ZJGSU 1737 链表

题目描述 请根据输入数据构造一个带头结点的单链表&#xff0c;链表结点的数据结构为struct node {int data; struct node *next;}&#xff0c;试设计算法&#xff1a;按递增次序输出单链表中各结点的数据元素&#xff0c;并释放结点所占用的存储空间。 要求&#xff1a;不允…...

Java开发人员不得不收集的代码,java软件开发面试常见问题

前言 今年的金三银四已经过去一大半了&#xff0c;在这其中参与过不少面试&#xff0c;2021都说工作不好找&#xff0c;这也是对开发人员的要求变向的提高了。 之前在Github上收获15Kstar的Java核心神技&#xff08;这参数&#xff0c;质量多高就不用我多说了吧&#xff09;非…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

一、WebRTC与智能硬件整合趋势​ 随着物联网和实时通信需求的爆发式增长&#xff0c;WebRTC作为开源实时通信技术&#xff0c;为浏览器与移动应用提供免插件的音视频通信能力&#xff0c;在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能&#xff0c;对实时…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...