LeetCode】寻找重复子树:深度解析与高效解法
📖 问题描述
给定一棵二叉树的根节点 root
,返回所有重复的子树。若两棵树结构相同且节点值相同,则认为它们是重复的。对于同类重复子树,只需返回其中任意一棵的根节点。
🌰 示例解析
示例1
输入:
1/ \2 3/ / \ 4 2 4/4
输出:[[2,4],[4]]
解释:
-
子树
[2,4]
出现在根节点左子节点和右子节点的左子节点位置 -
叶子节点
[4]
出现三次
示例2
输入:
2/ \1 1
输出:[[1]]
解释:两个叶子节点 [1]
结构相同
🛠️ 解题思路
核心思想:序列化 + 哈希表
-
序列化子树
将每个子树转化为唯一的字符串标识。通过递归遍历,生成形如根(左子树)(右子树)
的字符串,确保结构唯一性。 -
哈希表记录频次
使用哈希表存储序列化字符串及其对应的子树根节点。当某个序列化字符串第二次出现时,判定为重复子树。 -
去重处理
使用集合存储结果,避免同一类重复子树被多次记录。
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}class Solution {HashMap<String, TreeNode> map = new HashMap<>();Set<TreeNode> ans = new HashSet<>();public List<TreeNode> findDuplicateSubtrees(TreeNode root) {dfs(root);return new ArrayList<>(ans);}private String dfs(TreeNode root) {if (root == null) return "";StringBuilder sb = new StringBuilder();sb.append(root.val);sb.append("(");sb.append(dfs(root.left));sb.append(")(");sb.append(dfs(root.right));sb.append(")");String cur = sb.toString();if (map.containsKey(cur)) {ans.add(map.get(cur));} else {map.put(cur, root);}return cur;}
}
🔍 复杂度分析
-
时间复杂度:O(N²),每个节点需序列化其所有子节点。
-
空间复杂度:O(N²),哈希表存储所有子树序列化字符串。
💡 关键点解析
-
序列化设计
-
使用
根(左子树)(右子树)
格式确保结构唯一性。 -
空节点用空字符串表示,避免歧义。
-
-
哈希表去重
-
当同一序列化字符串首次出现时存入哈希表。
-
后续重复出现时,将首次记录的根节点加入结果集。
-
-
后序遍历优化
-
递归过程本质是后序遍历(先处理左右子树,再处理当前节点),确保子树序列化完整。
-
🚀 拓展思考
-
三元组优化
可引入唯一ID标识子树,用(根值, 左ID, 右ID)
代替长字符串,优化时间和空间复杂度至 O(N)。
📝 总结
通过序列化子树为唯一字符串,并结合哈希表记录出现频次,能够高效解决二叉树重复子树的查找问题。该解法思路清晰,代码简洁,适合作为面试快速解题方案。
相关文章:
LeetCode】寻找重复子树:深度解析与高效解法
📖 问题描述 给定一棵二叉树的根节点 root ,返回所有重复的子树。若两棵树结构相同且节点值相同,则认为它们是重复的。对于同类重复子树,只需返回其中任意一棵的根节点。 🌰 示例解析 示例1 输入: 1/ …...
[蓝桥杯] 挖矿(CC++双语版)
题目链接 P10904 [蓝桥杯 2024 省 C] 挖矿 - 洛谷 题目理解 我们可以将这道题中矿洞的位置理解成为一个坐标轴,以题目样例绘出坐标轴: 样例: 输入的5为矿洞数量,4为可走的步数。第二行输入是5个矿洞的坐标。输出结果为在要求步数…...
Appium如何实现移动端UI自动化测试?
🍅 点击文末小卡片,免费获取软件测试全套资料,资料在手,涨薪更快 Appium是一个开源跨平台移动应用自动化测试框架。 既然只是想学习下Appium如何入门,那么我们就直奔主题。文章结构如下: 为什么要使用A…...
在集合中哪些可以为null,哪些不能为null;Java 集合中 null 值允许情况总结与记忆技巧
Java 集合中 null 值允许情况总结与记忆技巧 一、核心集合对 null 的支持情况 集合类型Key 是否可为 nullValue 是否可为 null原因/备注HashMap✅ 是✅ 是对 null key 有特殊处理(存放在数组第 0 个位置)LinkedHashMap✅ 是✅ 是继承自 HashMapTreeMap…...
Python 并发编程指南:协程 vs 多线程及其他模型比较
Python 并发编程指南:协程 vs 多线程及其他模型比较 并发编程是指在单个程序中同时处理多个任务的能力,这些任务可以交替进行(同一时刻并不一定真的同时运行),而并行则强调在同一时刻真正同时运行多个任务(…...
WPS JS宏编程教程(从基础到进阶)-- 第五部分:JS数组与WPS结合应用
目录 摘要第5章 JS数组与WPS结合应用5-1 JS数组的核心特性核心特性解析5-2 数组的两种创建方式(字面量与扩展操作符)1. 字面量创建2. 扩展操作符创建5-3 数组创建应用:提取字符串中的数字需求说明代码实现5-4 用函数创建数组(new Array、Array.of、Array.from)1. new Arra…...
STM32定时器完全指南:从基础原理到高级应用 | 零基础入门STM32第九十六步
主题内容教学目的/扩展视频TIM定时器重点课程定时器,捕获器,比较器,PWM,单脉冲。高级TIM。定时器中断。了解TIM使用 师从洋桃电子,杜洋老师 📑文章目录 一、定时器核心原理1.1 硬件架构解析1.2 核心参数公式…...
Kafka分区机制详解:原理、策略与应用
#作者:张桐瑞 文章目录 一、分区的作用二、分区策略(一)轮询策略(二)随机策略(三)按消息键保序策略 三、实际案例:消息顺序问题的解决四、其他分区策略:基于地理位置的分…...
最小K个数
文章目录 题意思路代码 题意 题目链接 思路 代码 class Solution { public:vector<int> smallestK(vector<int>& arr, int k) {priority_queue<int> Q;for (auto &index:arr){Q.push(index);if (Q.size() > k)Q.pop();}vector<int> ans…...
【STL】list介绍(附与vector的比较)
文章目录 1.关于list2.使用2.1 list的构造2.2 list 迭代器的使用2.3 list 容量操作2.3.1 size()2.3.2 empty()2.3.3 resize() 2.4 list 元素访问2.4.1 front()2.4.2 back() 2.5 list 修改操作2.5.1 push_front()2.5.2 pop_front()2.5.3 push_back()2.5.4 pop_back()2.5.5 inser…...
音视频生命探测仪,救援现场的“视听先锋”|鼎跃安全
地震等自然灾害的突发性和破坏性对人类生命构成严重威胁。据统计,地震后的“黄金72小时”内,被困者的存活率随时间的推移急剧下降,因此快速、精准的搜救技术至关重要。 传统搜救手段依赖人耳识别呼救声或手动挖掘,效率低且易造成二…...
Arch视频播放CPU占用高
Arch Linux配置视频硬件加速 - DDoSolitary’s Blog 开源神器:加速你的视频体验 —— libvdpau-va-gl-CSDN博客 VDPAU(Video Decode and Presentation API for Unix) VA-API(Video Acceleration API) OpenGL 我的电…...
Python技巧:二维列表 和 二维矩阵 的区别
np.vstack 是 NumPy 中的一个函数,用于将多个数组沿垂直方向(行方向)堆叠。它可以处理 二维列表 和 二维矩阵,但它们之间有一些关键区别。以下是详细说明: 1. 二维列表 定义: 二维列表是 Python 原生的数据结构&#x…...
Linux 命令清单(Linux Command List)
测试人员必备的 Linux 命令清单文件管理 ls —— 显示目录内容。 ls -l 使用 -l 选项查看详细信息。 cd —— 改变当前工作目录。 cd /path/to/directory mkdir —— 创建新目录。 mkdir new_directory rm —— 删除文件或目录。 rm filename rm -r directory 使用 …...
Wallaby‘s: Nightmare (v1.0.2)靶场渗透
Wallabys: Nightmare (v1.0.2) 来自 <Wallabys: Nightmare (v1.0.2) ~ VulnHub> 1,将两台虚拟机网络连接都改为NAT模式 2,攻击机上做namp局域网扫描发现靶机 nmap -sn 192.168.23.0/24 那么攻击机IP为192.168.23.182,靶场IP192.168.23…...
java基础 可拆分迭代器 Spliterator<T>
Spliterator Spliterator介绍核心方法tryAdvanceforEachRemainingtrySplitestimateSizetrySplit 结合并行流(Parallel Stream)关键注意事项总结 Spliterator介绍 Spliterator(Splittable Iterator)是 Java 8 引入的接口ÿ…...
【AI提示词】决策专家
提示说明 决策专家可以帮助你进行科学决策,尽可能避免错误,提升决策成功的概率。 提示词 # Role : 决策专家决策,是面对不容易判断优劣的几个选项,做出正确的选择。说白了,决策就是拿个主意。决策专家是基于科学决策…...
VectorBT量化入门系列:第二章 VectorBT核心功能与数据处理
VectorBT量化入门系列:第二章 VectorBT核心功能与数据处理 本教程专为中高级开发者设计,系统讲解VectorBT技术在量化交易中的应用。通过结合Tushare数据源和TA-Lib技术指标,深度探索策略开发、回测优化与风险评估的核心方法。从数据获取到策略…...
Spring Boot 配置文件加载优先级全解析
精心整理了最新的面试资料和简历模板,有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 Spring Boot 配置文件加载优先级全解析 Spring Boot 的配置文件加载机制是开发者管理不同环境配置的核心功能之一。其通过外部化配置(Externaliz…...
System V 信号量:控制进程间共享资源的访问
System V 信号量:控制进程间共享资源的访问 在多进程操作系统中,当多个进程需要共享资源时,必须确保对资源的访问是有序的,以避免竞争条件(Race Condition)和数据不一致性问题。System V 信号量࿰…...
海运货代系统哪家好?能解决了哪些常见管理难题?
随着跨境电商的迅速发展,货代行业在全球供应链中扮演着越来越重要的角色。随着市场需求的多样化和国际运输环境的复杂化,货代企业面临的挑战也愈发复杂。为了应对这些挑战,数字化管理工具成为货代行业不可或缺的一部分。如今先进的海运货代系…...
预测性维护+智能优化:RK3568的储能双保险
在碳中和目标推动下,储能行业正经历前所未有的发展机遇。作为储能系统的核心组件,储能柜的智能化水平直接影响着整个系统的效率和安全性。RK3568智慧边缘控制器凭借其强大的计算能力、丰富的接口和高效的能源管理特性,正在成为工商储能柜的&q…...
蓝桥20257-元宵分配
#include <iostream> #include <bits/stdc.h> using namespace std; const int N1e910; typedef long long LL; int main() {// 请在此输入您的代码//将强其中的一碗全部倒进另一个中,将所有汤圆排序,最后选择前(N/2)…...
How to connect a mobile phone to your computer?
How to connect a mobile phone to your computer? 1. Background /ˈbkɡraʊnd/2. How to connect a mobile phone to your computer?References 1. Background /ˈbkɡraʊnd/ Let me introduce the background first. Today we will talk about this topic: How to conn…...
【力扣刷题实战】全排列II
大家好,我是小卡皮巴拉 文章目录 目录 力扣题目:全排列II 题目描述 解题思路 问题理解 算法选择 具体思路 解题要点 完整代码(C) 兄弟们共勉 !!! 每篇前言 博客主页:小卡…...
题目练习之map的奇妙使用
♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ ✨✨✨✨✨✨ 个…...
Excel 日期值转换问题解析
目录 问题原因 解决方案 方法1:使用 DateTime.FromOADate 转换 方法2:处理可能为字符串的情况 方法3:使用 ExcelDataReader 时的处理 额外提示 当你在 Excel 单元格中看到 2024/12/1,但 C# 读取到 45627 时,这是…...
Linux--文件系统
ok,上次我们提到了硬件和inode,这次我们继续学习文件系统 ext2文件系统 所有的准备⼯作都已经做完,是时候认识下文件系统了。我们想要在硬盘上存储文件,必须先把硬盘格式化为某种格式的文件系统,才能存储文件。文件系…...
2025 年福建交安安全员考试:结合本省交通特点备考
福建地处东南沿海,交通建设具有独特特点,这对交安安全员考试备考意义重大。在桥梁建设方面,由于面临复杂的海洋环境,桥梁的防腐、防台风等安全措施成为重点。考生在学习桥梁施工安全知识时,要特别关注福建本地跨海大桥…...
【项目管理】第6章 信息管理概论 --知识点整理
项目管理 相关文档,希望互相学习,共同进步 风123456789~-CSDN博客 (一)知识总览 项目管理知识域 知识点: (项目管理概论、立项管理、十大知识域、配置与变更管理、绩效域) 对应&…...
python-leetcode 66.寻找旋转排序数组中的最小值
题目: 已知一个长度为n的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组,例如,原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]若…...
WinMerge下载及使用教程(附安装包)
文章目录 一、WinMerge安装步骤1.WinMerge下载:2.解压:3.启动: 二、WinMerge使用步骤1.添加文件或文件夹2.查看差异3.格式选择 WinMerge v2.16.36 是一款免费开源的文件与文件夹比较、合并工具,能帮您快速找出差异,提高…...
Codeforces Round 1011 (Div. 2)
Dashboard - Codeforces Round 1011 (Div. 2) - Codeforces Problem - B - Codeforces 题目大意: 给你一个数组,你可以用一段子序列中没有出现的最小非负整数,替换数组中的组序列,经过若干操作,让数组变为长度为1,值…...
深度学习实战105-利用LSTM+Attention模型做生产车间中的铝合金生产时的合格率的预测应用
大家好,我是微学AI,今天给大家介绍一下深度学习实战105-利用LSTM+Attention模型做生产车间中的铝合金生产时的合格率的预测应用。 本项目利用LSTM+Attention模型对铝合金生产合格率进行预测,不仅在理论上具有创新性和可行性,而且在实际应用中也具有重要的价值和广阔的应用前…...
苹果内购支付 Java 接口
支付流程,APP支付成功后 前端调用后端接口,后端接口将前端支付成功后拿到的凭据传给苹果服务器检查,如果接口返回成功了,就视为支付。 代码,productId就是苹果开发者后台提前设置好的 产品id public CommonResult<S…...
Scrapy 是什么?Python 强大的爬虫框架详解
1. Scrapy 简介 Scrapy 是一个用 Python 编写的开源 网络爬虫框架,用于高效地从网站提取结构化数据。它提供了完整的爬虫开发工具,包括请求管理、数据解析、存储和异常处理等功能,适用于数据挖掘、监测和自动化测试等场景。 Scrapy 的核心特…...
一种用于基于扩散磁共振成像(MRI)的微观结构估计的外梯度与噪声调谐自适应迭代网络|文献速递-深度学习医疗AI最新文献
Title 题目 An extragradient and noise-tuning adaptive iterative network for diffusionMRI-based microstructural estimation 一种用于基于扩散磁共振成像(MRI)的微观结构估计的外梯度与噪声调谐自适应迭代网络 Background 背景 2.1. Advanced…...
需求的图形化分析-状态转换图
实时系统和过程控制应用程序可以在任何给定的时间内以有限的状态存在。当满足所定义的标准时,状态就会发生改变,例如在特定条件下,接收到一个特定的输入激励。这样的系统是有限状态机的例子。此外,许多业务对象(如销售…...
3月AI论文精选十篇
1. Feature-Level Insights into Artificial Text Detection with Sparse Autoencoders[1] 核心贡献:通过稀疏自编码器揭示AI生成文本的检测特征,提出基于特征分布的鉴别方法。研究发现,AI文本在稀疏编码空间中呈现独特的"高频低幅"…...
【android bluetooth 框架分析 01】【关键线程 2】【bt_stack_manager_thread线程介绍】
1. bt_stack_manager_thread bt_stack_manager_thread 是蓝牙协议栈中的核心调度线程,负责串行化处理协议栈的生命周期事件,包括初始化、启动、关闭与清理操作。它确保这些状态切换在同一线程中按顺序执行,避免竞态和资源冲突。作为蓝牙栈的…...
GEO, TCGA 等将被禁用?!这40个公开数据库可能要小心使用了
GEO, TCGA 等将被禁用?!这40个公开数据库可能要小心使用了 最近NIH公共数据库开始对中国禁用的消息闹得风风火火: 你认为研究者上传到 GEO 数据库上的数据会被禁用吗? 单选 会,毕竟占用存储资源 不会,不…...
matlab安装python API 出现Invalid version: ‘R2022a‘,
打开 setup.py 文件,找到设置版本号的部分 将 versionR2022a 修改为符合 Python 版本号规范的格式,例如 version2022.1 保存 setup.py 文件...
【ROS 通信】Services 服务通信
【ROS】Service 服务通信 前言前置操作创建一个 tutorial 功能包定义服务接口修改 CMakeLists.txt 文件修改 find_package修改 add_service_files修改 generate_messages修改 catkin_packagefind_package 和 catkin_package 修改 package.xml 文件构建 服务通信的 Python 实现服…...
25.4.8学习总结
javaFX实现倒计时 核心概念 Timeline: Timeline 是JavaFX动画API的核心类,用于创建动画。它可以按照指定的时间间隔(Duration)触发事件(KeyFrame)。 可以将其视为一个定时器,每隔一段时间执行一些操作。 …...
Android audio(6)-audiopolicyservice介绍
AudioPolicyService 是策略的制定者,比如某种 Stream 类型不同设备的音量(index/DB)是多少、某种 Stream 类型的音频数据流对应什么设备等等。而 AudioFlinger 则是策略的执行者,例如具体如何与音频设备通信,维护现有系…...
【区块链安全 | 第三十八篇】合约审计之获取私有数据(二)
文章目录 前言漏洞代码代码审计攻击步骤修复/开发建议审计思路 前言 在【区块链安全 | 第三十七篇】合约审计之获取私有数据(一)中,介绍了私有数据、访问私有数据实例、Solidity 中的数据存储方式等知识,本文通过分析具体合约代码…...
muduo:运行起来
Muduo 概述 Muduo 是一个用 C 编写的高性能网络库,由陈硕开发,主要用于开发 Linux 环境下的高性能网络应用程序。以下从几个方面对其进行详细介绍: 特点 事件驱动与非阻塞 I/O:Muduo 基于 Reactor 模式实现,使用了 …...
算法篇(八)【递归】
一、了解递归 1. 什么是递归? 递归就是自己调用自己 递归的概念解释起来就短短的几句话,但是写起来总是无从下手 ,但是首先要相信,在学过了数据结构 -- 树 之后 , 其实就已经具备了一定的递归思想,接下来的…...
Linux 学习笔记(4):cd 与 pwd 命令的深度解析与实战应用(期末、期中复习必备)
前言 一、cd 命令:切换工作目录的利器 1.命令来源与基本语法 2.命令使用示例 3.相对路径与绝对路径的使用 二、pwd 命令:清晰定位当前工作目录 1.命令来源与基本语法 2.命令使用示例 三、结语 前言 在 Linux 系统的操作中,对工作目录的…...
眨眼睛查看密码工具类
“眨眼睛查看密码”工具类实现思路: 一、核心功能 实现点击眼睛图标切换密码明文/星号显示,提升表单输入体验。包含以下关键功能: • 初始状态:密码框显示为星号,闭眼图标可见。 • 点击闭眼图标:切换为明…...