当前位置: 首页 > 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 精密测量六、需要捕获瞬态信号值的应用七、需要高…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...