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

学习记录:js算法(四十七):相同的树

文章目录

    • 相同的树
      • 我的思路
      • 网上思路
        • 队列
        • 序列化方法
    • 总结

相同的树

给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

图一:
在这里插入图片描述

图二:
在这里插入图片描述

图三:
在这里插入图片描述

示例 1:图一
输入:p = [1,2,3], q = [1,2,3]
输出:true示例 2:图二
输入:p = [1,2], q = [1,null,2]
输出:false示例 3:图三
输入:p = [1,2,1], q = [1,1,2]
输出:false

我的思路
递归
网上思路

我的思路

var isSameTree = function (p, q) {if (p === null && q === null) {return true;}if (p === null || q === null) {return false;}if (p.val !== q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

讲解
基本情况:

  • 如果 p 和 q 都是 null,返回 true。
  • 如果只有一个是 null,返回 false。
  • 如果两个节点的值不同,返回 false。
    递归:
  • 递归调用 isSameTree 来比较左子树和右子树。
  • 只有当左子树和右子树都相同时,整个树才相同。

网上思路

队列
 var isSameTree = function (p, q) {const queue = [[p, q]]; // 初始化队列,存储节点对while (queue.length > 0) {const [node1, node2] = queue.shift(); // 从队列中取出一对节点// 如果两个节点都是 null,继续比较下一个if (node1 === null && node2 === null) {continue;}// 如果只有一个节点是 null,或者值不同,返回 falseif (node1 === null || node2 === null || node1.val !== node2.val) {return false;}// 将左右子节点加入队列queue.push([node1.left, node2.left]);queue.push([node1.right, node2.right]);}return true; // 如果遍历完成都没有发现不同,返回 true
}

讲解

  1. 初始化队列 创建一个队列,将两棵树的根节点 pq 成对放入队列。
  2. 循环遍历 当队列不为空时,进行以下操作:
    2.1. 取出节点对 从队列中取出一对节点 node1node2
    2.2. 检查是否都为 null 如果 node1node2 都是 null,继续下一对节点的比较。
    2.3. 检查是否有一个为 null 如果只有一个节点是 null,或两个节点的值不同,返回 false
    2.4. 入队左右子节点 如果两个节点都存在,将它们的左右子节点成对放入队列。
  3. 返回结果 如果队列处理完毕且没有发现不同,返回 true
序列化方法
var isSameTree = function (p, q) {function serialize(root) {if (root === null) {return 'null,'; // 用 'null' 表示空节点}// 先序遍历,节点值与左右子树的序列化结果return root.val + ',' + serialize(root.left) + serialize(root.right);}// 序列化两棵树并比较return serialize(p) === serialize(q);
};

讲解
序列化函数 serialize(root):

  • 编写一个辅助函数,将二叉树转换为字符串。可以使用前序遍历(pre-order traversal)来实现。
  • 如果当前节点是 null,返回字符串 ‘null,’。
  • 否则,返回当前节点的值与左右子树的序列化结果,使用逗号 , 分隔。
    主函数 isSameTree(p, q):
  • 调用 serialize 函数对两棵树进行序列化。
  • 比较两个序列化后的字符串,若相同则返回 true,否则返回 false。

总结

序列化的方法看起来挺不错的

相关文章:

学习记录:js算法(四十七):相同的树

文章目录 相同的树我的思路网上思路队列序列化方法 总结 相同的树 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 图一: 图二&…...

使用Hutool-poi封装Apache POI进行Excel的上传与下载

介绍 Hutool-poi是针对Apache POI的封装,因此需要用户自行引入POI库,Hutool默认不引入。到目前为止,Hutool-poi支持: Excel文件(xls, xlsx)的读取(ExcelReader)Excel文件(xls&…...

asp.net core grpc快速入门

环境 .net 8 vs2022 创建 gRPC 服务器 一定要勾选Https 安装Nuget包 <PackageReference Include"Google.Protobuf" Version"3.28.2" /> <PackageReference Include"Grpc.AspNetCore" Version"2.66.0" /> <PackageR…...

拿到一个新项目,如何开展测试

1. 拿到一个新的项目或者新的需求&#xff0c;首先需要搞清楚他的背景、目标和需求&#xff0c;这个过程需要和产品、开发、客户去沟通。 2. 清楚需求后&#xff0c;首先将业务流程走通&#xff0c;确保项目的基础功能是正常的 3. 根据项目需求明确测试的目标&#xff0c;如&…...

pre-commit 的配置文件

这个文件是 pre-commit 的配置文件&#xff0c;通常命名为 .pre-commit-config.yaml。pre-commit 是一个用于管理和维护多种预提交钩子的框架&#xff0c;旨在在代码提交&#xff08;git commit&#xff09;之前自动执行一系列检查和格式化任务&#xff0c;以确保代码质量和一致…...

5G-A和F5G-A,对于AI意味着什么?

2024年已经过去了一大半&#xff0c;风起云涌的AI浪潮&#xff0c;又发生了不小的变化。 一方面&#xff0c;AI大模型的复杂度不断提升&#xff0c;模型参数持续增加&#xff0c;智算集群的规模也随之增加。万卡级、十万卡级集群&#xff0c;已经逐渐成为训练标配。这对智算网络…...

vue-实现rtmp直播流

1、安装vue-video-player与videojs-flash npm install vue-video-player -S npm install videojs-flash --save 2、在main.js中引入 3、组件中使用 这样就能实现rtmp直播流在浏览器中播放&#xff0c;但有以下几点切记&#xff0c;不要入坑 1.安装vue-video-player插件一定…...

论文阅读【时间序列】ModerTCN (ICLR2024)

【时间序列】ModerTCN (ICLR2024) 原文链接&#xff1a;ModernTCN: A Modern Pure Convolution Structure for General Time Series Analysis 代码仓库&#xff1a;ModerTCN 简易版本实现代码可以参考&#xff1a;&#xff08;2024 ICLR&#xff09;ModernTCN&#xff1a;A Mod…...

Robot Operating System——二维平面中的位置和方向

大纲 应用场景1. 移动机器人导航场景描述具体应用 2. 自动驾驶车辆控制场景描述具体应用 3. 机器人运动规划场景描述具体应用 4. 室内导航场景描述具体应用 5. 仿真环境场景描述具体应用 定义字段解释 案例 geometry_msgs::msg::Pose2D 是 ROS 2 中的一个消息类型&#xff0c;用…...

一文带你读懂分库分表,分片,Sharding的许多概念

一文带你读懂分库分表,分片,Sharding的许多概念 分库是将一个库拆分为多个库&#xff0c;分表就是将一个表拆分为多个表。分库分表有垂直拆分和水平拆分。垂直拆分一般是按照业务将表分到不同的库中&#xff08;此种不在本发的讨论范围&#xff09;。水平拆分是将表的数据拆分…...

算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?

算法实战(五):如何用学过的数据结构和算法实现一个短网址系统? 在互联网时代,我们经常会遇到一些很长的网址,不仅不便于记忆,而且在一些场合下可能会受到长度限制。短网址系统就是为了解决这个问题而产生的。本文将介绍如何用学过的数据结构和算法实现一个短网址系统,…...

Python 环境搭建

Python 环境搭建 本章节我们将向大家介绍如何在本地搭建Python开发环境。 Python可应用于多平台包括 Linux 和 Mac OS X。 你可以通过终端窗口输入 “python” 命令来查看本地是否已经安装Python以及Python的安装版本。 Python下载 Python最新源码&#xff0c;二进制文档&am…...

uniapp vue3 使用echarts绘制图表 柱状图等

部分内容AI总结 Uniapp 使用 Vue3 和 ECharts 组件的总结 在 Uniapp 中使用 Vue3 和 ECharts 进行数据可视化是一种常见需求。以下将详细介绍如何在 Uniapp 项目中安装 ECharts 插件、在 main.js 中挂载 ECharts 以及一个简单的示例 demo。 1. 下载 ECharts 插件 在 Uniapp 中…...

字符串处理的艺术:深入探索charAt(), indexOf(), nextLine(), 和 next() 的应用与组合

摘要 本文旨在深入探讨Java中字符串处理的核心方法——charAt(), indexOf(), nextLine(), 和 next()&#xff0c;通过实例展示这些方法如何协同工作以解决复杂的字符串处理任务。我们将从基础概念出发&#xff0c;逐步构建到高级应用&#xff0c;包括字符串的遍历、搜索、读取…...

C#八股总结

重载和重写的区别 方法重载&#xff1a;在同一个类中定义多个同名但参数不同的方法。 方法重写&#xff1a;通过使用 virtual 和 override 关键字&#xff0c;实现基类和派生类之间的方法重写。 重载发生在同类中&#xff0c;重写发生在父子类中 重载方法名相同参数不同&#…...

iOS 中的 sqlite-shm 和 sqlite-wal 文件丢失

iOS 中的 sqlite-shm 和 sqlite-wal 文件丢失或损坏可能会导致 NSManagedObjectContext 的 performAndWait 方法抛出 NSInternalInconsistencyException 异常。这是因为这些文件在 SQLite 的 Write-Ahead Logging (WAL) 模式下起着关键作用&#xff0c;Core Data 依赖它们来确保…...

ubuntu22上C/C++程序使用weston+wayland+OpenGLES渲染

一&#xff0c;安装依赖软件&#xff1a;sudo apt install zlib1g-dev libssl-dev libgles2-mesa-dev libsystemd-dev libpng-dev libglib2.0-dev libwayland-dev weston libweston-9-dev 二&#xff0c;启动&#xff1a; # 运行weston weston -Swayland-1# 运行程序 ./yourp…...

打点 - 泛微 E-Cology WorkflowServiceXml

请求路径 /services%20/WorkflowServiceXml显示如下&#xff0c;漏洞可能存在 利用&#xff1a; 根据提示在 CMD 处输入 Memshell 注入内存马&#xff0c;并点击执行&#xff0c;成功注入 冰蝎配置&#xff0c;输入内存马地址 成功连接 命令执行...

Go语言接口与多态

Go语言虽然并非传统意义上的面向对象语言&#xff0c;但它通过接口&#xff08;Interface&#xff09;和匿名组合&#xff08;Composition&#xff09;等机制&#xff0c;实现了类似面向对象编程中的多态性&#xff08;Polymorphism&#xff09;。接口和多态性是Go语言中非常重…...

【ADC】SAR 型 ADC 和 ΔΣ ADC 的选型决策方法

本文学习于TI 高精度实验室课程&#xff0c;介绍如何选择 SAR 或 delta-sigma 型 ADC。 文章目录 一、选型决策树二、特定传感器的应用三、需要 DC 精度但分辨率较低的应用四、需要 DC 精度且分辨率较高的应用五、极低噪声的 DC 精密测量六、需要捕获瞬态信号值的应用七、需要高…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...