算法通关村第五关-二叉树遍历(层数优先)之经典问题:简单的层序遍历、层序遍历分层、自底向上的层序遍历
基础知识(青铜挑战)
-
了解二叉树的基础知识
实战训练(白银挑战)
简单的层序遍历
-
基本的层序遍历思路很清晰:
-
给你一个二叉树根节点,你需要创建一个队列 queue 来遍历节点,一个链表 list 来存储节点的数据域,即值
-
首先将根节点入队
-
队列 queue 出队,将该节点值存入 list,再依次将左右孩子节点入队
-
重复以上操作,每个节点出对后,都存储该节点值到 list 中,再依次将左右孩子节点入队,直到队列 queue为空
-
这样得到的数据链表 list 就是按层序遍历的顺序得到的
-
-
具体代码如下:(2023/09/09午)
public static List<Integer> simpleLevelOrder(TreeNode root) {if (root == null) {return new ArrayList<Integer>();}
List<Integer> res = new ArrayList<Integer>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中,然后不断遍历队列queue.add(root);//有多少元素执行多少次while (queue.size() > 0) {//获取当前队列的长度,这个长度相当于 当前这一层的节点个数TreeNode t = queue.remove();res.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}return res;}
层序遍历分层
-
层序遍历我们做到了,这里添加一个要求:对层序遍历的节点值分层处理,即二叉树每层的节点值分别存放进一个链表 list 中
-
这个代码怎么写呢?很简单的,按这个思路走:
-
我们之前层序遍历时,每出队一个节点,都把其值存入 list 链表中,然后入队其孩子节点
-
在开始出队某一层的节点时,此时队列的节点数,就是二叉树这一层的节点数
-
那我们根据可以某时刻队列容量来遍历队列,将这层的节点全部出队,并且把节点值存入该层独有的 list 中
-
当然了,每个节点出队后,要将自己的孩子节点依次入队
-
这样,当队列为空时,我们得到了各层的节点链表 list,返回一个包含各层 list 的 list 即可
-
-
具体代码如下:(2023/09/09晚)
public static List<List<Integer>> level102Order(TreeNode root) {if (root == null) {return new ArrayList<List<Integer>>();}
List<List<Integer>> res = new ArrayList<List<Integer>>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中,然后不断遍历队列queue.add(root);while (queue.size() > 0) {//获取当前队列的长度,这个长度相当于 当前这一层的节点个数int size = queue.size();ArrayList<Integer> tmp = new ArrayList<Integer>();//将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中//如果节点的左/右子树不为空,也放入队列中for (int i = 0; i < size; ++i) {TreeNode t = queue.remove();tmp.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}//将临时list加入最终返回结果中res.add(tmp);}return res;}
自底向上的层序遍历
-
在前面学习的基础上,实现这个要求就很简单了
-
在拿到各层节点值的 list 后,按头插的方式,插入链表 list 中,就实现了自底向上的层序遍历了(2023/09/09晚)
-
具体代码如下:
public static List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();if (root == null) {return levelOrder;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();level.add(node.val);TreeNode left = node.left, right = node.right;if (left != null) {queue.offer(left);}if (right != null) {queue.offer(right);}}levelOrder.add(0, level);//栈}return levelOrder;}
相关文章:
算法通关村第五关-二叉树遍历(层数优先)之经典问题:简单的层序遍历、层序遍历分层、自底向上的层序遍历
基础知识(青铜挑战) 了解二叉树的基础知识 实战训练(白银挑战) 简单的层序遍历 基本的层序遍历思路很清晰: 给你一个二叉树根节点,你需要创建一个队列 queue 来遍历节点,一个链表 list 来存储…...
C++左右值及引用
1 左值和右值 简单记法:能取地址的是左值,不能取地址的是右值 右值一般是常量 例: i 是右值,因为先把 i 赋值给临时变量,临时变量在1,而临时变量是将亡值,&i取地址会报错 i是左值…...
如何备份和恢复数据库
目录 1.xtrabackup 是什么2.全量备份3.增量备份4.使用备份进行恢复5.原理6.参考 本文主要介绍如何使用xtrabackup 进行数据库的备份和恢复,并在最后介绍了原理。 1.xtrabackup 是什么 XtraBackup是由Percona开发的一款开源的MySQL数据库备份工具。它可以对InnoDB和…...
简化数据库操作:探索 Gorm 的约定优于配置原则
文章目录 使用 ID 作为主键数据库表名TableName临时指定表名列名时间戳自动填充CreatedAtUpdatedAt时间戳类型Gorm 采用约定优于配置的原则,提供了一些默认的命名规则和行为,简化开发者的操作。 使用 ID 作为主键 默认情况下,GORM 会使用 ID 作为表的主键: type User st…...
保姆级Anaconda安装教程
一.anaconda下载 建议使用清华大学开源软件镜像站进行下载,使用官网下载速度比较慢。 anaconda清华大学开源软件镜像站 : https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 一路next即可,注意添加环境变量得选项都勾上。 二.验证…...
你写过的最蠢的代码是?——后端篇
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页: 🐅🐾猫头虎的博客🎐《面试题大全专栏》 🦕 文章图文并茂🦖…...
快速幂
876. 快速幂求逆元 - AcWing题库 AC代码: #include <iostream> #include <cstring> #include <algorithm>using namespace std;typedef long long ll;int n;int qmi(int a,int k,int p) {int res1;while(k){if(k&1)res(ll)res*a%p;k>&…...
【题解 动态规划】 Colored Rectangles
题目描述: 分析: 乍一看我还以为是贪心! 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据 19 19 19 19 20 20 20 20如果按照贪心的做法,答案是20*20*2 但是其实答案是19*20*4 因此这道题用贪心是不对的 于是我…...
VsCode好用的扩展插件
开发插件推荐: 别名路径跳转 >> 点击引用的变量名,ctrl 点击 跳转文件Auto Rename Tag >> 修改标签前缀,后缀标签会同时修改Chinees 中文(简体)Code Runner >> 纯js文件右键点击run code即可底部终端打印file-icons-mac >> ma…...
Linux shell编程学习笔记4:修改命令行提示符格式(内容和颜色)
一、命令行提示符格式内容因shell类型而异 Linux终端命令行提示符内容格式则因shell的类型而异,例如CoreLinux默认的shell是sh,其命令行提示符为黑底白字,内容为: tcbox:/$ 其中,tc为当前用户名,box为主机…...
vue-引入使用main.js全局常量
common.js 命名什么都可以,用来定义常量的 定义了之后使用export让此暴露出去 const QRaddress http://localhost:9875export{QRaddress, } main.js //引入刚刚的js import {QRaddress} from /config/common.js挂载 Vue.prototype.$QRaddress QRaddress使用 …...
【C语言】【动态内存管理】malloc,free,calloc,realloc
1.malloc函数 void* malloc(size_t size)功能:向内存申请字节为 size大小的空间 使用时要包含头文件:<stdlib.h> 开辟成功:返回开辟好的空间初始地址的指针 开辟失败:返回空指针 NULL 使用举例: (malloc和free…...
Linux性能优化--性能工具-系统CPU
2.0.概述 本章概述了系统级的Linux性能工具。这些工具是你追踪性能问题时的第一道防线。它们能展示整个系统的性能情况和哪些部分表现不好。 1.理解系统级性能的基本指标,包括CPU的使用情况。 2.明白哪些工具可以检索这些系统级性能指标。 2.1CPU性能统计信息 为…...
Ipython和Jupyter Notebook介绍
Ipython和Jupyter Notebook介绍 Python、IPython和Jupyter Notebook是三个不同但密切相关的工具。简而言之,Python是编程语言本身,IPython是对Python的增强版本,而Jupyter Notebook是一种在Web上进行交互式计算的环境,使用IPytho…...
数列极差(c++题解)
题目描述 佳佳的老师在黑板上写了一个由 n个正整数组成的数列,要求佳佳进行如下操作:每次擦去其中的两个数a 和b ,然后在数列中加入一个数a*b1 ,如此下去直至黑板上剩下一个数为止,在所有按这种操作方式最后得到的数…...
面试题:熟悉设计模式吗?谈谈简单工厂模式和策略模式的区别
刚刚接触设计模式的时候,我相信单例模式和工厂模式应该是用的最多的,毕竟很多的底层代码几乎都用了这些模式。自从接触了一次阿里的公众号发的一次文章关于 DDD的使用 以后,就逐渐接触了策略模式。现在在项目中运用最多的也是这几种设计模式了…...
Windows + Git + TortoiseGit + Github
一、下载Git(Git For Windows) 1.1. Git下载地址:https://gitforwindows.org/ 1.2. 默认安装即可(包名:Git-2.42.0.2-64-bit.exe) 二、下载TortoiseGit 2.1.TortoiseGit下载地址:http://tortoi…...
MySQL数据库索引练习
1.学生表:Student (Sno, Sname, Ssex , Sage, Sdept) 学号,姓名,性别,年龄,所在系 Sno为主键 课程表:Course (Cno, Cname,) 课程号,课程名 Cno为主键 学生选课表:SC (Sno, Cno, Scor…...
mysql面试题10:MySQL中有哪几种锁?表级锁、行级锁、页面锁区别和联系?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Mysql中有哪几种锁? 在MySQL中,主要有以下几种类型的锁: 共享锁(Shared Lock):也称为读锁。多个事务可以同时持有共享锁,可以读取但不能修…...
ctfshow—1024系列练习
1024 柏拉图 有点像rce远程执行,有四个按钮,分别对应四份php文件,开始搞一下。一开始,先要试探出 文件上传到哪里? 怎么读取上传的文件? 第一步:试探上传文件位置 直接用burp抓包,…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
