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

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...