LeetCode算法题(Go语言实现)_34
题目
考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。
一、代码实现
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {// 递归法遍历叶子节点(网页3、5)var getLeaves func(root *TreeNode) []intgetLeaves = func(root *TreeNode) []int {if root == nil {return []int{}}if root.Left == nil && root.Right == nil {return []int{root.Val}}// 左子树优先遍历保证顺序(网页2、3)return append(getLeaves(root.Left), getLeaves(root.Right)...)}leaves1 := getLeaves(root1)leaves2 := getLeaves(root2)return reflect.DeepEqual(leaves1, leaves2)
}
二、算法分析
1. 核心思路
- 深度优先遍历:递归遍历二叉树,优先访问左子树,确保叶子节点按从左到右顺序收集
- 序列比对:比较两棵树的叶子值序列是否完全一致
2. 关键步骤
- 递归终止条件:空节点返回空数组,叶子节点返回自身值
- 递归分解:将左右子树的叶子序列合并
- 最终比对:使用
reflect.DeepEqual
判断切片相等性
3. 复杂度
指标 | 值 | 说明 |
---|---|---|
时间复杂度 | O(n) | 每个节点访问一次,n为节点总数 |
空间复杂度 | O(h) | h为树的高度(递归栈空间) |
三、图解示例
以二叉树root1 = [3,5,1,6,2,9,8,null,null,7,4]
和root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
为例:
四、边界条件与扩展
1. 特殊场景验证
- 空树对比:
root1=nil, root2=nil
→ true - 结构不同但叶序相同:如
root1=[1,2,3], root2=[1,3,2]
→ false - 单节点树:
root1=[5], root2=[5]
→ true
2. 多语言实现
# Python实现(网页2、3)
class Solution:def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:def dfs(node):if not node: return []if not node.left and not node.right: return [node.val]return dfs(node.left) + dfs(node.right)return dfs(root1) == dfs(root2)
// Java实现(网页4)
class Solution {public boolean leafSimilar(TreeNode root1, TreeNode root2) {List<Integer> list1 = new ArrayList<>();List<Integer> list2 = new ArrayList<>();dfs(root1, list1);dfs(root2, list2);return list1.equals(list2);}private void dfs(TreeNode node, List<Integer> list) {if (node == null) return;if (node.left == null && node.right == null) list.add(node.val);dfs(node.left, list);dfs(node.right, list);}
}
五、总结与扩展
1. 核心创新点
- 递归分治策略:将复杂问题分解为子树处理
- 顺序保障机制:左子树优先遍历确保叶序一致性
- 内存优化设计:Go语言切片操作避免全局变量
2. 扩展应用
- 并行遍历优化:使用协程同时遍历两棵树,实时比对叶子值
- 非递归实现:用栈模拟递归过程,避免栈溢出风险
- 流式处理:边遍历边比较,提前终止不匹配的情况
3. 工程优化方向
- 内存预分配:根据树高度预切片容量(Go语言)
- 迭代器模式:实现叶子节点迭代器支持大规模数据处理
- 并发安全:添加互斥锁支持多线程环境下的遍历
相关文章:
LeetCode算法题(Go语言实现)_34
题目 考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。 如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true&…...
# 项目部署指南:Flask、Gradio与Docker实现流程
Python项目部署指南:Flask、Gradio与Docker实践 1. 引言 在机器学习和Web开发中,将模型或应用部署为在线服务是关键一步。本文将介绍如何使用 Flask 和 Gradio 快速构建前端界面,并通过 Docker 容器化实现高效部署,涵盖完整流程图…...
2022第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组(题解解析)
记录刷题的过程、感悟、题解。 希望能帮到,那些与我一同前行的,来自远方的朋友😉 大纲: 1、九进制转十进制-(解析)-简单的进制转化问题😄 2、顺子日期-(解析)-考察日期 3…...
UML之序列图的参与者与生命线
序列图是建模过程中必选的一种描述行为的手段,它展示在某些有用的行为中元素之间的消息交换和相互作用。交互是构成行为的一个单元;这些元素必须是可连接元素,通常将这些可连接元素称为交互中的参与者(Participants)。…...
基于Python Flask快速构建网络安全工具资源库的Web应用实践
引言 在网络安全领域,信息收集(OSINT)是渗透测试、漏洞挖掘和威胁分析的关键环节。然而,面对海量工具和分散的技术文档,安全研究人员常需耗费大量时间查找和比对工具信息。本文将介绍如何利用 Python Flask HTML 技…...
xv6-labs-2024 lab1
lab-1 注:实验环境在我的汇编随手记的末尾部分有搭建教程。 0.前置 第零章 xv6为我们提供了多种系统调用,其中,exec将从某个文件里读取内存镜像(这确实是一个好的说法),并且将其替换到调用它的内存空间,也就是这个…...
HTTP Form v.s. Flask-WTF Form v.s. Bootstrap Form
在Flask-WTF和Bootstrap 的Form创建中,添加了页面显示Flash Messages。 相比Flask_WTF, Bootstrap用 render_form(form)渲染样式,自动带错误提示,不需要像Flask_WTF那样手写 for error in ... 。 项目结构: register_app/ ├── HTTP_Form_App.py ├── FlaskWTF_Form…...
Linux网络编程——https的协议及其加密解密方式
目录 一、前言 https协议 常见的加密方式 1、对称加密 2、非对称加密 3、数字签名 1. 只用对称加密 2、只用单一的非对称加密 3、双方都使用非对称加密 4、非对称加密对称加密 证书 证书颁发流程 服务器与客户端的证书验证流程 5、证书非对称加密对称加密 前言 上一…...
Node.js 下载与安装(图文)
下载 官网:【直达:https://nodejs.org/en/】。 点击【Download】,选择【版本,系统】。点击【Windows Installer(.msi)】。 安装 双击【.msi文件】,选择【安装路径】,也可以一直【下一步】。 查看版本 …...
3.31-4.06 Web3 游戏周报:Pebble 玩家留存率登顶,Treasure DAO 面临重组危机
回顾上周的区块链游戏概况,查看 Footprint Analytics 与 ABGA 最新发布的数据报告。 【3.31–4.06】Web3 游戏行业动态 链游生态系统 Treasure DAO 因财务危机面临重组,将终止游戏运营和 Treasure Chain3A 链游 Shrapnel 开发商 Neon Machine 深陷财务…...
echarts生成3D立体地图react组件
地图散点图效果: react项目中安装echarts、echarts-gl依赖: npm install echarts echarts-gl 文件目录结构: 地图组件map目录下文件代码,点击散点图圆点触发事件handleCityClick: index.jsx: import { …...
Node.js 中处理 Excel 文件的最佳实践
在现代应用开发中,Excel 文件仍然是数据交换和存储的重要格式之一。在 Node.js 环境中,处理 Excel 文件的需求日益增加。本文将介绍如何在 Node.js 中高效地处理 Excel 文件,涵盖工具选择、基本操作和最佳实践。 1. 选择合适的库 在 Node.js…...
解决Ubuntu系统鼠标不流畅的问题
电脑是联想的台式组装机,安装ubuntu系统(不管是16、18、20、22)后,鼠标都不流畅。最近几天想解决这个问题,于是怀疑到了显卡驱动上。怀疑之前一直用的是集成显卡,而不是独立显卡,毕竟2060的显卡…...
【Linux】虚拟机设置静态IP
主播我今天下午学了几节微服务课,上课的时候,直接把手机拿走了去上课(电脑连的我手机的热点),虚拟机没关,晚上主播我回来继续学,电脑连上热点之后,发现虚拟机连接不上了,…...
Web API:AbortController
Web API:AbortController 主要用途基本工作原理基本用法示例高级用例1. 实现请求超时2. 取消多个请求3. 与其他异步 API 一起使用 浏览器支持总结 主要用途 AbortController 是一个 Web API,主要用于取消一个或多个 Web 请求(如 fetch 请求&…...
服务器配置虚拟IP
服务器配置虚拟IP的核心步骤取决于具体场景,主要包括本地单机多IP配置和高可用集群下的虚拟IP管理两种模式。 一、本地虚拟IP配置(单服务器多IP) 基于Linux系统: 确认网络接口:使用 ip addr 或 ifconfig 查…...
《AI大模型应知应会100篇》第5篇:大模型发展简史:从BERT到ChatGPT的演进
第5篇:大模型发展简史:从BERT到ChatGPT的演进 摘要 近年来,人工智能领域最引人注目的进步之一是大模型(Large Language Models, LLMs)的发展。这些模型不仅推动了自然语言处理(NLP)技术的飞跃&…...
小球反弹(蓝桥杯C语言)
有一长方形,长为 343720343720 单位长度,宽为 233333233333 单位长度。在其内部左上角顶点有一小球 (无视其体积),其初速度如图所示且保持运动速率不变,分解到长宽两个方向上的速率之比为 dx:dy15:17dx:dy15:17。小球碰到长方形的…...
Java面试39-Zookeeper中的Watch机制的原理
Zookeeper是一个分布式协调组件,为分布式架构下的多个应用组件提供了顺序访问控制能力。它的数据存储采用了类似于文件系统的树形结构,以节点的方式来管理存储在Zookeeper上的数据。 Zookeeper提供了一个Watch机制,可以让客户端感知到Zooke…...
3️⃣ Coze工作流基础教学(2025年全新版本)
目录 一、什么是工作流 二、为什么用工作流 三、工作流使用场景 四、怎么学习工作流 五、工作流功能概述 六、制作工作流基础流程 6.1 创建工作流 6.2 配置工作流 6.3 调试工作流 6.4 发布工作流 6.5 使用工作流 6.6 复制工作流 6.7 删除工作流 6.8 设置工作流异…...
备战蓝桥杯——走迷宫问题(BFS解决)
这是一个经典的BFS算法 1. BFS算法保证最短路径 核心机制:广度优先搜索按层遍历所有可能的路径,首次到达终点的路径长度即为最短步数。这是BFS的核心优势。队列的作用:通过队列按先进先出的顺序处理节点,确保每一步探索的都是当…...
usbip学习记录
USB/IP: USB device sharing over IP make menuconfig配置: Device Drivers -> Staging drivers -> USB/IP support Device Drivers -> Staging drivers -> USB/IP support -> Host driver 如果还有作为客户端的需要,继续做以下配置&a…...
mlir-tblgen 的应用渐进式示例
示例01 -gen-dialect-decls toy_dia.1.toy include "mlir/IR/OpBase.td" //include "mlir/IR/FunctionInterfaces.td" //include "mlir/IR/SymbolInterfaces.td" //include "mlir/Interfaces/SideEffectInterfaces.td"def Toy_Diale…...
AI大模型与未来社会结构的重构:从工具到共生体
一、引言:从蒸汽机到ChatGPT,文明的每一次跃迁都始于“工具的自我进化” 历史长河中,每一次技术革命,都伴随着人类社会组织、认知方式乃至价值体系的巨变。从18世纪的蒸汽机到20世纪的信息技术,再到21世纪的人工智能&…...
2015年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2015年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛(China Undergraduate Mathematical Contest in Modeling)是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动,目的在于激励学生学习数学的积极性,提高学…...
免费Deepseek-v3接口实现Browser-Use Web UI:浏览器自动化本地模拟抓取数据实录
源码 https://github.com/browser-use/web-ui 我们按照官方教程,修订几个环节,更快地部署 步骤 1:克隆存储库 git clone https://github.com/browser-use/web-ui.git cd web-ui Step 2: Set Up Python Environment 第 2 步:设置…...
Bash判断命令是否存在
在 Bash 脚本里,你可以通过多种方法判断某个命令是否存在。下面为你详细介绍几种常见的判断方式。 1. 使用command -v command -v命令能够返回指定命令的可执行文件路径,如果该命令不存在则不会有输出。借助这一特性,我们可以结合条件判断语…...
双指针(滑动窗口)
用于在数组或字符串的进行快速排序 匹配 排序或移动操作。 双指针不是真的指针,只是用两个变量来表示下标(在后面都用指针来表示) 双指针往往和单调性 排序 联系在一起,暴力往往是O(n方)双指针利用单调性可以优化到o(n) 有对撞指针 快慢指针 美丽区间…...
在PPT中同时自动播放多个视频的方法
在PPT中同时自动播放多个视频的方法 文章目录 在PPT中同时自动播放多个视频的方法1 准备视频2 设置动画为“出现”3 设置所有视频为“自动播放”4 最终效果与其他设置 在PPT制作的过程中,我们经常遇到需要同时自动播放多个视频的情况。本文将详细介绍实现这种效果的…...
使用 Vue 快速集成 FullCalendar 日历组件教程
FullCalendar 是一款功能强大的 JavaScript 日历组件,支持 React/Vue 等主流框架,提供丰富的日历视图和交互功能。本文将手把手教你在 Vue 项目中快速集成,并演示核心功能实现。 📦 主要特性亮点 ✅ 月/周/日多视图切换 ✅…...
xv6-labs-2024 lab2
lab-2 0. 前置 课程记录 操作系统的隔离性,举例说明就是,当我们的shell,或者qq挂掉了,我们不希望因为他,去影响其他的进程,所以在不同的应用程序之间,需要有隔离性,并且࿰…...
redis导入成功,缺不显示数据
SpringBootTest class SecurityApplicationTests {AutowiredStringRedisTemplate template; //添加这句代码,自动装载,即可解决文章三处代码报错Testvoid contextLoads() {String compact Jwts.builder().signWith(Jwts.SIG.HS512.key().build()).subj…...
Flink对比Spark streaming、Storm
对比Spark streaming、Storm 产品 模型 语义 容错机制 状态管理 延时 吞吐量 Storm native at-least-once ack 无 low low Spark streaming micro-batch exactly-once RDD checkpoint 有 medium high Flink native exactly-once checkpoint 有 low …...
力扣316去除重复字母-单调栈
题目来源: 给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。 示例 1: 输入:s "bcabc" 输出ÿ…...
第421场周赛:数组的最大因子得分、
Q1、数组的最大因子得分 1、题目描述 给你一个整数数组 nums。 因子得分 定义为数组所有元素的最小公倍数(LCM)与最大公约数(GCD)的 乘积。 在 最多 移除一个元素的情况下,返回 nums 的 最大因子得分。 注意&…...
COMSOL 与人工智能融合的多物理场应用:28个案例的思路、方法与工具概述
应用案例概述 基于 COMSOL 与人工智能(AI)结合的应用案例涵盖了 28 个多领域场景,包括工程(如热传导优化、结构力学预测)、能源(如电池热管理、燃料电池性能)、生物医学(如药物传递…...
【算法】插入排序
算法系列五:插入排序 一、直接插入排序 1.原理 2.实现 3.性质 3.1时间复杂度 3.2空间复杂度 3.3稳定性 二、希尔排序 1.原理 1.1优化方向 1.2优化原理 2.设计 2.1比较无序时 2.2比较有序时 3.实现 4.性质 4.1时间复杂度 4.2空间复杂度 4.3稳定性…...
企业展示型网站模板HTML5网站模板下载指南
在当今数字化浪潮中,企业网站已成为企业展示形象、推广产品和服务的重要窗口。一个设计精美、功能完善的企业展示型网站,不仅能提升企业的品牌形象,还能吸引潜在客户,促进业务增长。而HTML5网站模板,凭借其跨平台兼容性…...
C盘清理——快速处理
C盘清理 | 快速处理 软件:小番茄C盘清理 https://ccleancdn.xkbrowser.com/cleanmaster/FanQieClean_13054_st.exe 前言:为什么需要专业的C盘清理工具? 作为一位长期与Windows系统打交道的技术博主,我深知C盘空间不足带来的痛苦…...
什么是模型驱动开发MDD?有哪些应用场景?
模型驱动开发(Model-Driven Development,MDD)是一种以模型为核心的软件开发方法,其核心思想是通过创建高层次的抽象模型来描述系统的结构和行为,而非直接编写代码。这些模型经过自动化工具的转换或生成,最终…...
uniapp小程序生成海报/图片并保存分享
调研结果: 方法一:canvasuni.canvasToTempFilePath耗时太长,现在卡在canvas的绘制有问题,canvas绘制的部分东西不生效但是找不到原因 方法二:使用wxml-to-canvas其实也差不多是用canvas手动绘制,可能会卡在…...
从IoT到AIoT:智能边界的拓展与AI未来趋势预测
文章目录 引言:从连接万物到感知万物1. AIoT的本质:将智能嵌入万物2. AIoT的推动力量与挑战2.1 推动力量2.2 关键挑战 3. 五大AIoT未来趋势预测趋势一:边缘智能将成为主流架构趋势二:AI模型将向自适应与多任务演进趋势三ÿ…...
2012年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2012年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛(China Undergraduate Mathematical Contest in Modeling)是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动,目的在于激励学生学习数学的积极性,提高学…...
2140 星期计算
2140 星期计算 ⭐️难度:中等 🌟考点:2022、思维、省赛 📖 📚 1️⃣法一: 同余定理, import java.util.Scanner;public class Main2 {public static void main(String[] args) {Scanner sc …...
NVIDIA Jetson 环境安装指导 PyTorch | Conda | cudnn | docker
本文适用于Jetson Nano、TX1/TX2、Xavier 和 Orin系列的设备,供大家参考。 1、PyTorch不同版本安装 这里适用于Jetson Nano、TX1/TX2、Xavier 和 Orin ,需要JetPack 4.2以上。 下载地址:PyTorch for Jetson - Jetson & Embedded System…...
理解 Rust 中的 String 分配机制
在 Rust 中,哪怕是一行再普通不过的代码,也可能暗藏玄机。这次我们就来剖析这样一句看似简单的代码: let s "hello world".to_string();这行代码触发了 只读数据段(.rodata)、堆(heap࿰…...
园区网拓扑练习
1.拓扑图要求 1.按照图示的VLAN及IP地址需求,完成相关配需 2、要求SW1为VLAN 2/3的主根及主网关,SW2为vlan 20/30的主根及主网关,SW1和SW2互为备份 3.上层通过静态路由协议完成数据通信过程 4.AR1为企业出口路由器 5.要求全网可达 2.需求分…...
CentralCache
目录 一、Span和Spanlist 二、CentralCache 一、Span和Spanlist CentralCache其实也是哈希桶结构,只不过他是一个个的Span(Span是管理一定数量的页的结构),而且Span会管理一个freelist,用来挂起一个个的小内存块给Th…...
STM32 基础1
什么是GPIO的上拉和下拉电阻 下拉电阻:把一个不确定的信号通过电阳连接到地,其实就是初始化为低电平。 上拉电阻:把一个不确定的信号通过电连接到高电平,其实就是初始化为高电平。 本质:上拉地注入电流,下…...
Python爬虫第5节-urllib的异常处理、链接解析及 Robots 协议分析
目录 一、处理异常 1.1 URLError 1.2 HTTPError 二、解析链接 2.1 urlparse() 2.2 urlunparse() 2.3 urlsplit() 2.4 urlunsplit() 2.5 urljoin() 2.6 urlencode() 2.7 parse_qs() 2.8 parse_qsl() 2.9 quote() 2.10 unquote() 三、分析网站Robots协议 3.1 R…...