【数据结构与算法 | 队列篇】力扣102, 107

1. 力扣102 : 二叉树的层序遍历

(1). 题

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

示例 1:

fbf1c4f33ddc948c764e9c9237acd91c.jpeg

输入: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

(2). 思路

由题,可知方法返回一个集合,该集合的元素仍然是一个集合. 该题需要用到队列数据结构.如果二叉树是空树,直接返回空集合. 如果不是,则将根节点入队.由于根节点在队列中,将size初始化为1,n的作用则是用于更新size.while循环,只要队列不为空,那么就new一个集合,for循环依次出队,并将出队的节点的值add到集合中收集起来,如果其有左孩子或右孩子,则将该孩子节点入队,并将n++. 一次循环结束时,将小集合add入大集合中.

(3). 解

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> bl = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();if(root == null) {return bl;}deque.offer(root);int size = 1;int n = 0;//只要队列不为空while(!deque.isEmpty()) {List<Integer> l = new ArrayList<>();for(int i =0 ; i < size; i++) {TreeNode tn = deque.poll();l.add(tn.val);if(tn.left != null) {deque.offer(tn.left);n++;}if(tn.right != null) {deque.offer(tn.right);n++;}}size = n;n = 0;bl.add(l);}return bl;}
}

2. 力扣107 : 二叉树的层序遍历2

(1). 题

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

示例 1:

d247066a47d3d1cfeceba712880b907d.jpeg

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

示例 2:

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

示例 3:

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

提示:

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

(2). 思路

该题与力扣102题同源,只不过最后处理的时候多了一个出栈入栈的操作而已. 所以完全可以将102题的代码复制粘贴过来,然后添加一个栈结构,while循环中,不是直接将小集合添加到大集合中,而是做一个压栈的操作.while循环结束以后,将栈中元素全部弹出,add入大集合,将其返回即可.

(3). 解

/*** 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>> levelOrderBottom(TreeNode root) {List<List<Integer>> bl = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();Deque<List<Integer>> stack = new LinkedList<>();if(root == null) {return bl;}deque.offer(root);int size = 1;int n = 0;//只要队列不为空while(!deque.isEmpty()) {List<Integer> l = new ArrayList<>();for(int i =0 ; i < size; i++) {TreeNode tn = deque.poll();l.add(tn.val);if(tn.left != null) {deque.offer(tn.left);n++;}if(tn.right != null) {deque.offer(tn.right);n++;}}size = n;n = 0;stack.push(l);}while(!stack.isEmpty()) {bl.add(stack.pop());}return bl;}
}

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

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

相关文章

树莓集团:构筑全国数字影像生态链

在数字化浪潮席卷全球的今天&#xff0c;数字影像技术正以前所未有的速度改变着我们的生活。成都树莓集团以远见卓识和坚定步伐&#xff0c;专注于全国数字影像生态链的建设&#xff0c;不断推动着文创产业的创新与发展。 树莓集团致力于打造一个完整的数字影像生态链&#xff…

FreeRTOS基础(三):动态创建任务

上一篇博客&#xff0c;我们讲解了FreeRTOS中&#xff0c;我们讲解了创建任务和删除任务的API函数&#xff0c;那么这一讲&#xff0c;我们从实战出发&#xff0c;规范我们在FreeRTOS下的编码风格&#xff0c;掌握动态创建任务的编码风格&#xff0c;达到实战应用&#xff01; …

解决kettle界面右上角的connect消失——且使用admin登录不上Kettle资源库

一、问题描述 1.1、Kettle界面右上角的connect消失了 当我们配置Kettle界面的资源库(Other Repositories)内容后,Kettle界面右上角的connect消失了;如下图所示: 1.2、使用默认的账户【admin】和密码【admin】登录不上kettle资源库 当我们切换到我们配置的数据库使用超管账…

AGM DAP-LINK 离线烧录报错信息分析

DAP-LINK 支持离线烧录。 即&#xff1a;先把要烧录的bin 烧录到DAP-LINK 中&#xff1b;然后DAP-LINK 可以脱离PC&#xff0c;上电后通过按键对目标板进行烧录。 CMSIS-DAP模式 跳线JGND断开&#xff0c;状态LED D4快闪&#xff0c;D3常亮&#xff08;串口状态&#xff09;。…

Android关闭硬件加速对PorterDuffXfermode的影响

Android关闭硬件加速对PorterDuffXfermode的影响 跑的版本minSdk33 编译SDK34 import android.content.Context import android.graphics.Bitmap import android.graphics.Canvas import android.graphics.Color import android.graphics.Paint import android.graphics.Port…

LabVIEW与欧陆温控表通讯的实现与应用:厂商软件与自主开发的优缺点

本文探讨了LabVIEW与欧陆温控表通讯的具体实现方法&#xff0c;并对比了使用厂商提供的软件与自行开发LabVIEW程序的优缺点。通过综合分析&#xff0c;帮助用户在实际应用中选择最适合的方案&#xff0c;实现高效、灵活的温控系统。 LabVIEW与欧陆温控表通讯的实现与应用&#…

【Linux】网络高级IO

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;Linux 目录 &#x1f449;&#x1f3fb;五种IO模型&#x1f449;&#x1f3fb;消息通信的同步异步与进程线程的同步异步有什么不同&#xff1f;&#x1f449…

YOLOv8改进(一)-- 轻量化模型ShuffleNetV2

文章目录 1、前言2、ShuffleNetV2代码实现2.1、创建ShuffleNet类2.2、修改tasks.py2.3、创建shufflenetv2.yaml文件2.4、跑通示例 3、碰到的问题4、目标检测系列文章 1、前言 移动端设备也需要既准确又快的小模型。为了满足这些需求&#xff0c;一些轻量级的CNN网络如MobileNe…

【2024新版】银系统源码/超市收银系统/智慧新零售/ERP进销存管理/线上商城/商户助手

>>>系统简述&#xff1a;本系统适用于超吃便利店&#xff0c;美妆母婴行业&#xff0c;服装鞋帽行业&#xff0c;食品零售行业&#xff0c;3C数码电子行业&#xff0c;食品生鲜等一切零售行业&#xff0c;产品功能角色介绍如下 合伙人&#xff1a;无限发展代理商和商…

OpenMV学习笔记3——画图函数汇总

画图&#xff0c;即在摄像头对应位置画出图形&#xff0c;对于需要反馈信息的程序来说很直观。就如上一篇文章颜色识别当中的例子一样&#xff0c;我们在识别出的色块上画出矩形方框&#xff0c;并在中间标出十字&#xff0c;可以直观的看到OpenMV现在识别出的色块。 目录 一…

Nginx源码编译安装

Nginx NginxNginx的特点Nginx的使用场景Nginx 有哪些进程 使用源码编译安装Nginx准备工作安装依赖包编译安装Nginx检查、启动、重启、停止 nginx服务配置 Nginx 系统服务方法一&#xff1a;方法二&#xff1a; 访问Nginx页面 升级Nginx准备工作编译安装新版本Nginx验证 Nginx N…

安卓启动 性能提升 20-30% ,基准配置 入门教程

1.先从官方下载demohttps://github.com/android/codelab-android-performance/archive/refs/heads/main.zip 2.先用Android studio打开里面的baseline-profiles项目 3.运行一遍app&#xff0c;这里建议用模拟器&#xff0c;&#xff08;Pixel 6 API 34&#xff09;设备运行&a…

未来已来:Spring Boot引领数据库智能化革命

深入探讨了Spring Boot如何与现代数据库技术相结合&#xff0c;预测并塑造未来的数据访问趋势。本书不仅涵盖了Spring Data JPA的使用技巧&#xff0c;还介绍了云原生数据库的概念&#xff0c;微服务架构下的数据访问策略&#xff0c;以及AI在数据访问层的创新应用。旨在帮助开…

【docker】docker的安装

如果之前安装了旧版本的docker我们需要进行卸载&#xff1a; 卸载之前的旧版本 卸载 # 卸载旧版本 sudo apt-get remove docker docker-engine docker.io containerd runc # 卸载历史版本 apt-get purge docker-ce docker-ce-cli containerd.io docker-buildx-plugin docker…

Redis学习笔记【实战篇--短信登录】

开篇导读 实战篇有什么样的内容 短信登录 这一块我们会使用redis共享session来实现 商户查询缓存 通过本章节&#xff0c;我们会理解缓存击穿&#xff0c;缓存穿透&#xff0c;缓存雪崩等问题&#xff0c;让小伙伴的对于这些概念的理解不仅仅是停留在概念上&#xff0c;更…

mfc140u.dll丢失的解决方法有哪些?怎么全面修复mfc140u.dll文件

mfc140u.dll丢失其实相对来说不太常见到&#xff0c;因为这个文件一般是不丢失的&#xff0c;不过既然有人遇到这种问题&#xff0c;那么小编一定满足各位&#xff0c;给大家详细的唠叨一下mfc140u.dll丢失的各种解决方法&#xff0c;教大家以最快最有效率的方法去解决mfc140u.…

Low Memory Killer in Android

目录 低内存管理&#xff08;Linux vs Android&#xff09; Linux内存回收 shrink_slab原理 shrink_zone原理 oom killer oom killer设计原则 OOM killer具体实现 android的lmk(Low Memory Killer) Android系统特点 oom killer在android中的不足 ​​​​​​​LMK概…

探索 Python 的 vars() 函数

大家好&#xff0c;在软件开发的过程中&#xff0c;调试是一个不可或缺的环节。无论你是在解决 bug&#xff0c;优化代码&#xff0c;还是探索代码的执行流程&#xff0c;都需要一些有效的工具来帮助你更好地理解和调试代码。在 Python 编程中&#xff0c;vars() 函数是一个非常…

国产可视化爬虫助力AI大模型训练:精准爬取汉语词典

大语言模型&#xff0c;可以生成流畅对话的会话聊天机器人、通畅起草文章的内容生成器。在炫酷技术的背后&#xff0c;数据、算力、算法&#xff0c;被视作生成式AI的三个核心要素。由此可见&#xff0c;高质量的训练数据对于AI算法的准确性至关重要。 如何获得高质量的训练数…

【嵌入式硬件】DRV8874电机驱动

目录 1 芯片介绍 1.1 特性简介 1.2 引脚配置 1.3 最佳运行条件 2 详细说明 2.1 PMODE配置控制模式 2.1.1 PH/EN 控制模式 2.1.2 PWM 控制模式 2.1.3 独立半桥控制模式 2.2 电流感测和调节 2.2.1 IPROPI电流感测 2.2.2 IMODE电流调节 3.应用 3.1设计要求 3.2 设计…