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

代码随想录训练营day15|102.层序遍历 226.翻转二叉树 101.对称二叉树

@TOC


前言

代码随想录算法训练营day15


一、Leetcode 102.层序遍历

1.题目

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

示例 1:

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

示例 2:

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

示例 3:

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

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/binary-tree-level-order-traversal

2.解题思路

方法一:广度优先搜索

思路和算法

我们可以用广度优先搜索解决这个问题。

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时候我们可以利用哈希表,维护一个以 level 为键,对应节点值组成的数组为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可。

考虑如何优化空间开销:如何不用哈希映射,并且只用一个变量 node 表示状态,实现这个功能呢?

我们可以用一种巧妙的方法修改广度优先搜索:

首先根元素入队
当队列不为空的时候求当前队列的长度 sisi​依次从队列中取 sisi​ 个元素进行拓展,然后进入下一次迭代

它和普通广度优先搜索的区别在于,普通广度优先搜索每次只取一个元素拓展,而这里每次取 sisi​ 个元素。在上述过程中的第 ii 次迭代就得到了二叉树的第 ii 层的 sisi​ 个元素。

为什么这么做是对的呢?我们观察这个算法,可以归纳出这样的循环不变式:第 ii 次迭代前,队列中的所有元素就是第 ii 层的所有元素,并且按照从左向右的顺序排列。证明它的三条性质(你也可以把它理解成数学归纳法):

初始化:i=1i=1 的时候,队列里面只有 root,是唯一的层数为 11 的元素,因为只有一个元素,所以也显然满足「从左向右排列」;
保持:如果 i=ki=k 时性质成立,即第 kk 轮中出队 sksk​ 的元素是第 kk 层的所有元素,并且顺序从左到右。因为对树进行广度优先搜索的时候由低 kk 层的点拓展出的点一定也只能是 k+1k+1 层的点,并且 k+1k+1 层的点只能由第 kk 层的点拓展到,所以由这 sksk​ 个点能拓展到下一层所有的 sk+1sk+1​ 个点。又因为队列的先进先出(FIFO)特性,既然第 kk 层的点的出队顺序是从左向右,那么第 k+1k+1 层也一定是从左向右。至此,我们已经可以通过数学归纳法证明循环不变式的正确性。
终止:因为该循环不变式是正确的,所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此,我们证明了算法是正确的。

3.代码实现

```java class Solution { public List> levelOrder(TreeNode root) { List> ret = new ArrayList>(); if (root == null) { return ret; }

Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int currentLevelSize = queue.size();for (int i = 1; i <= currentLevelSize; ++i) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}ret.add(level);}return ret;
}

}

```

二、Leetcode 226.翻转二叉树

1.题目

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1:

输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]

示例 2:

输入:root = [2,1,3] 输出:[2,3,1]

示例 3:

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

提示:

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

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/invert-binary-tree

2.解题思路

方法一:递归

这是一道很经典的二叉树问题。显然,我们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转。如果当前遍历到的节点 rootroot 的左右两棵子树都已经翻转,那么我们只需要交换两棵子树的位置,即可完成以 rootroot 为根节点的整棵子树的翻转。

3.代码实现

```java class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }

```

三、Leetcode 101.对称二叉树

1.题目

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3] 输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3] 输出:false

提示:

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

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/symmetric-tree

2.解题思路

方法一:递归

思路和算法

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

fig1

因此,该问题可以转化为:两个树在什么情况下互为镜像?

如果同时满足下面的条件,两个树互为镜像:

它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称

fig2

我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,pp 指针和 qq 指针一开始都指向这棵树的根,随后 pp 右移时,qq 左移,pp 左移时,qq 右移。每次检查当前 pp 和 qq 节点的值是否相等,如果相等再判断左右子树是否对称。

3.代码实现

```java class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); }

public boolean check(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}

}

```

相关文章:

代码随想录训练营day15|102.层序遍历 226.翻转二叉树 101.对称二叉树

TOC 前言 代码随想录算法训练营day15 一、Leetcode 102.层序遍历 1.题目 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 (即逐层地&#xff0c;从左到右访问所有节点)。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a…...

Nginx 配置https以及wss

一、申请https证书 可以在阿里云申请免费ssl证书&#xff0c;一年更换一次 二、Nginx配置ssl upstream tomcat_web{server 127.0.0.1:8080; }server {listen 443 ssl;server_name www.xxx.com;## 配置日志文件access_log /var/log/nginx/web/xxx-ssl-access.log main;er…...

Log4net在.Net Winform项目中的使用

引言&#xff1a; Log4net是一个流行的日志记录工具&#xff0c;可以帮助开发人员在应用程序中实现高效的日志记录。本文将提供一个详细的分步骤示例&#xff0c;来帮助您在.Net Winform项目中使用Log4net。 目录 一、安装Log4net二、配置Log4net三、在项目中使用Log4net四、初…...

从零到一制作扫雷游戏——C语言

什么是扫雷游戏&#xff1f; 扫雷游戏作为一种老少咸宜的益智游戏&#xff0c; 它的游戏目标十分简单&#xff0c;就是要求玩家在最短的时间内&#xff0c; 根据点击格子之后所出现的数字来找出所有没有炸弹的格子&#xff0c; 同时在找的时候要避免点到炸弹&#xff0c;一…...

Python 数据挖掘与机器学习教程

详情点击链接&#xff1a;Python 数据挖掘与机器学习教程 模块一&#xff1a;Python编程 Python编程入门 1、Python环境搭建&#xff08; 下载、安装与版本选择&#xff09;。 2、如何选择Python编辑器&#xff1f;&#xff08;IDLE、Notepad、PyCharm、Jupyter…&#xff…...

排序小白必读:掌握插入排序的基本原理

一、插入排序是什么&#xff1f; 它是一种简单直观的排序算法。类似于整理扑克牌&#xff0c;想象你手上有一堆未排序的牌&#xff0c;你将它们逐个插入已排序的牌堆中的正确位置。拿起一张牌&#xff0c;与已排序的牌进行比较&#xff0c;将它插入到合适的位置。重复这个过程…...

html常见兼容性问题

1. png24位的图片在iE6浏览器上出现背景 解决方案&#xff1a;做成PNG8&#xff0c;也可以引用一段脚本处理. 2. 浏览器默认的margin和padding不同 解决方案&#xff1a;加一个全局的 *{margin:0;padding:0;} 来统一。 3. IE6双边距bug&#xff1a;在IE6下&#xff0c;如果对…...

Docker实战:docker compose 搭建Redis

1、配置文件准备 redis 配置文件&#xff1a;https://pan.baidu.com/s/1YreI9_1BMh8XRyyV9BH08g2、创建目录并赋权 mkdir -p /home/docker/redis/data /home/redis/logs /home/redis/conf chmod -R 777 /home/docker/redis/data* chmod -R 777 /home/docker/redis/logs*3、re…...

Debian11 Crontab

Crontab用户命令 可执行文件 crontab命令的可执行文件在哪儿&#xff1f; $ which -a crontab /usr/bin/crontab /bin/crontabcrontab命令的可执行文件有2个&#xff1a;/usr/bin/crontab 和 /bin/crontab $ diff /usr/bin/crontab /bin/crontab $diff 发现这两个文件并无区…...

css 文字排版-平铺

序&#xff1a; 1、表格的宽度要有&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 2、容器不能是display:inline 3、扩展---》node全栈框架 代码 text-align-last: justify; width: 70px; display: inline-block; 主要是用于表单左侧文字排序&#xff01;...

把握潮流:服装定制小程序的发展与趋势

随着互联网的快速发展&#xff0c;小程序成为了人们生活中不可或缺的一部分。尤其在服装行业&#xff0c;定制化已经成为了一种趋势。为了满足消费者个性化的需求&#xff0c;服装定制小程序应运而生。 为了方便开发者的设计和制作&#xff0c;我们可以使用第三方的制作平台来创…...

Go 安装配置

介绍Ubuntu20.04 安装和配置Go 可以参考官网的这个为 Go 开发配置Visual Studio Code - Go on Azure | Microsoft Learn 1.安装Go 去这个地方下载Go https://go.dev/doc/install 如果之前安装过&#xff0c;可以参考这个&#xff08;没有可以忽略&#xff09; 下载完成后执…...

镜像底层原理详解和基于Docker file创建镜像

目录 一、镜像底层原理 1.联合文件系统(UnionFS) 2.镜像加载原理 3.为什么Docker里的centos的大小才200M? 二、Dockerfile 1.简介 2.Dockerfile操作常用命令 &#xff08;1&#xff09;FORM 镜像 &#xff08;2&#xff09;MAINTAINER 维护人信息 &#xff08;3&…...

k8s扩缩容与滚动更新

使用kubectl run创建应用 kubectl run kubernetes-bootcamp \> --imagedocker.io/jocatalin/kubernetes-bootcamp:v1 \> --port8080 端口暴露出去 kubectl expose pod kubernetes-bootcamp --type"NodePort" --port 8080 使用kubectl create创建应用 kubect…...

4.小程序的运行机制

启动过程 把小程序的代码包下载到本地解析app.json全局配置文件执行app.js小程序入口文件&#xff0c;调用App()创建小程序的实例渲染小程序首页小程序启动完成 页面渲染过程 加载解析页面的.json配置文件加载页面.wxml模板和.scss样式执行页面的.ts文件&#xff0c;调用Pag…...

基于 Vercel TiDB Serverless 的 chatbot

作者&#xff1a; shiyuhang0 原文来源&#xff1a; https://tidb.net/blog/7b5fcdc9 # 前言 TiDB Serverless 去年就有和 Vercel 的集成了&#xff0c;同时还有一个 bookstore template 方便大家体验。但个人感觉 bookstore 不够炫酷&#xff0c;借 2023 TiDB hackthon 的…...

Android 多渠道打包及VasDolly使用

目录 1.添加productFlavors的配置buildConfigFieldmanifestPlaceholdersresValue 2.设置apk文件的名称&#xff0c;便于识别3.添加vasdolly、添加gradle脚本&#xff08;windows&#xff09; 作用&#xff1a;一次性可以打多个apk包&#xff0c;名字、包名、logo等可以不相同。…...

LeetCode 42题:接雨水

题目 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,…...

spring boot 提示:程序包不存在,解决方法总结

背景&#xff1a; 之前出现过这样的问题&#xff0c;打包安装父项目就好了&#xff0c;今天改了一下代码&#xff0c;重新编译的时候&#xff0c;又出现了这样的情况&#xff0c;决定深度挖掘一下这里面的问题 spring boot 提示&#xff1a;程序包不存在&#xff0c;解决方法总…...

docker项目实战

1、使用mysql:5.6和 owncloud 镜像&#xff0c;构建一个个人网盘 1&#xff09;拉取mysql:5.6和owncloud镜像 [rootmaster ~]# docker pull mysql:5.6 5.6: Pulling from library/mysql 35b2232c987e: Pull complete fc55c00e48f2: Pull complete 0030405130e3: Pull compl…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...