[E二叉树] lc572. 另一棵树的子树(dfs+前中序判断+树哈希+树上KMP+好题)
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:572. 另一棵树的子树
2. 题目解析
看到这个题目就感觉不简单,因为写了写 dfs 版本的,发现好像不太会…
还是简单粗暴一点,直接搞一个 前序+中序,进行判断即可。我们知道通过 前序+中序,是可以构建出一颗唯一的二叉树的,当然可以通过 前序+中序,去判断两颗二叉树是不是一样的。
但这里需要注意的是:
- 我们需要将 NULL 的位置也通过占位标记记录一下,不然无法判断子树完全相等,只能判断出来存在相同的子结构。例如:


但这里需要判断两个 vector a、b,b 是否在 a 中出现…这个东西写起来比较耗性能。但在这还是过了。算是一个思路吧。
dfs:
每个点,都可能是目标子树的根节点,同时我们需要判断当根节点确定时,该根节点的子树是否等于目标子树。故需要两个递归函数:
- dfs 函数:遍历树上所有节点,判断以该节点作为根节点,它的子树是否有包含目标子树。
- 先判断当前根节点是否可以作为目标子树的根节点。
- 再判断根节点的左子树、右子树下的所有节点是否可以作为目标子树的根节点。
- check 函数:判断节点所处子树是否等于目标子树。
至于其他的写法,看官解吧。还是很秀的…
评论区有提到 树上 HASH 的方法字节面试过…让写一下…
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
前、中 序判断二叉树。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> a1, a2, b1, b2;void dfs1(TreeNode* root, vector<int> &v) {if (!root) {v.push_back(1e9); return;}v.push_back(root->val);dfs1(root->left, v);dfs1(root->right, v);}void dfs2(TreeNode* root, vector<int> &v) {if (!root) {v.push_back(1e9); return;}dfs2(root->left, v);v.push_back(root->val);dfs2(root->right, v);}bool check(vector<int> &a, vector<int>& b) {int n = a.size(), m = b.size();for (int i = 0; i < n; i ++ ) {bool flag = false;for (int k = i, j = 0; k < n && j < m; j ++ , k ++ ) {if (a[k] != b[j]) {break;}if (j == m - 1) flag = true;}if (flag) return true;}return false;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {dfs1(root, a1);dfs2(root, a2);dfs1(subRoot, b1);dfs2(subRoot, b2);return check(a1, b1) && check(a2, b2);}
};
dfs:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool check(TreeNode* root, TreeNode* subRoot) {if (!root && !subRoot) return true;if (!root && subRoot) return false;if (root && !subRoot) return false;if (root->val != subRoot->val) return false;// 同步判断子结构是否一致return check(root->left, subRoot->left) && check(root->right, subRoot->right);}// 判断树 root 下是否存在 subRoot 结构的子树bool dfs(TreeNode* root, TreeNode* subRoot) {if (!root) return false;// 先判断root根是否可以作为目标子树的根// root根无法作为目标子树根,目标子树根可能存在root的左子树、右子树当中// dfs 判断左子树 是否存在目标子树// dfs 判断右子树 是否存在目标子树return check(root, subRoot) || dfs(root->left, subRoot) || dfs(root->right, subRoot);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {return dfs(root, subRoot);}
};
相关文章:
[E二叉树] lc572. 另一棵树的子树(dfs+前中序判断+树哈希+树上KMP+好题)
文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:572. 另一棵树的子树 2. 题目解析 看到这个题目就感觉不简单,因为写了写 dfs 版本的,发现好像不太会… 还是简单粗暴一点,直接搞一个 前序中序,进行判断即可。我…...
C# 设计模式之简单工厂模式
总目录 前言 本文是个人基于C#学习设计模式总结的学习笔记,希望对你有用! 1 基本介绍 简单工厂模式 定义:用于创建对象,将对象的创建与使用分离。 简单工厂模式中用于创建实例的方法是静态(static)方法,因而简单工厂…...
mac中dyld[5999]: Library not loaded: libssl.3.dylib解决方法
需要重新安装下openssl3.0版本 brew reinstall openssl3.0 安装后执行还是报错,需要找到openssl的安装路径 /opt/homebrew/Cellar/openssl3.0/3.0.14/lib/ 将libssl.3.dylib和libcrypto.3.dylib拷贝到自己的二进制文件同目录下,再执行二进制文件就可…...
python 容器
文章目录 数据容器特点比较通用序列操作示例代码1. s.index(x[, i[, j]])2. s.count(x)示例代码注意事项代码解释输出结果 数据容器的通用转换1. list()2. tuple()3. str()4. set()5. dict()6. enumerate()7. zip()8. sorted()9. reversed()10. map()11. filter()12. join()示例…...
微信小程序中Component中如何监听属性变化
1.在父组件的.json文件中引入子组件: "usingComponents": {"articleList":"../../components/articleList/articleList",}2.在父组件中给子组件绑定数据 <articleList num"{{number}}"></articleList>3.子组…...
【Python 逆向滑块】(实战五)逆向滑块,并实现用Python+Node.js 生成滑块、识别滑块、验证滑块、发送短信
逆向日期:2024.08.03 使用工具:Python,Node.js 本章知识:滑块距离识别,滑块轨迹生成,验证滑块并获取【validate】参数 文章难度:中等(没耐心的请离开) 文章全程已做去敏处…...
微服务架构设计的最佳实践
在当今快速变化的软件开发环境中,微服务架构因其灵活性、可扩展性和可维护性而逐渐成为大型分布式系统的首选架构模式。然而,成功实施微服务架构并非易事,它要求开发团队遵循一系列最佳实践来确保系统的可靠性、效率和可管理性。本文将探讨微…...
样式与特效(3)——实现一个测算页面
这次我们使用前端实现一个简单的游戏页面,理论上可以增加很多玩法,,但是这里为了加深前端的样式和JS点击事件,用该案例做练习。 首先需要掌握手机端的自适应,我们是只做手机端玩家页面 。需要允许自适应手机端页面, 用…...
芯片制造过程4光刻机
以下内容均取自哔哩哔哩up主谈三圈 链接: 芯片制造详解04:光刻技术与基本流程|国产之路不容易 1.光刻原理 通过光掩膜、光刻机、光刻胶进行光刻 光掩膜是芯片的蓝图,是一张刻有集成电路板图的玻璃遮光板光刻机就像一台纳米级的打印机&#…...
Nexus3 Repository代理pypi设置与应用
目录 1. 创建Blob库并指定路径 2. 创建pypi阿里镜像源 3. 创建pypi腾讯镜像源 4. 创建一个pypi组管理 5. 配置pip 6. 下载测试 扩展:配置好后无法下载解决思路。 Nexus 存储库中的 Blob 存储是指一种用于存储大量非结构化数据的技术。在 Nexus 存储库的上下文…...
PMP–知识卡片--燃起图
燃起图用两条曲线分别绘制随时间的推移、完成的工作量和总工作量的变化情况。它不仅能清晰地展示项目进度,还是对团队成员的一种激励形式。 使用燃起图可以更好地了解进度、范围变更和预期完成时间,它为所有相关方提供了更清晰的进度状态。 燃起图根据工…...
63 epoll服务器 (ET模式)
基于LT模式修改,并加入前面的应用层计算器,实现稍完整的服务器功能 1.修改tcp_socket.hpp,新增非阻塞读和非阻塞写接口 2.对于accept返回的new_sock加上EPOLLET这样的选项 注意:此代码暂时未考虑listen_sock ET的情况,…...
AI Agent
一,什么是AI Agent? AI Agent(人工智能代理)是一种能够自主执行任务和决策的智能系统。它通常具备感知环境、处理信息和采取行动的能力,能够模拟人类的思维和行为方式。 它可以是软件程序,也可以是嵌入式…...
select
select函数简介: select是Linux中常用的多路复用IO机制,它允许程序同时监控多个文件描述符(可以是套接字socket,也可以是普通文件)的读、写和异常事件。 #include <sys/select.h> #include <sys/time.h> …...
按照指定格式打印pprint()
【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 按照指定格式打印 pprint() [太阳]选择题 根据给定的Python代码,哪个选项是正确的? from pprint import pprint data { name: A, age: 30, hobbies:…...
Study--Oracle-07-ASM常用维护操作(五)
一、ASM创建新的磁盘组 1、查看系统中可用的磁盘 set lines 150; col name for a35; col path for a35; select group_number,path, state, name, total_mb, free_mb from v$asm_disk; 2、磁盘组操作 创建磁盘组 create DISKGROUP DATADGV2 EXTERNAL REDUNDANCY DISK /dev…...
[Git][分支管理][上]详细讲解
目录 1.理解分支2.创建分支3.切换分支4.合并分支5.删除分支 1.理解分支 感性理解:分支可以理解为平行宇宙,但是在用户需要的时候,可以将两个平行宇宙合并,此时两个平行宇宙的效果将会"叠加"理性理解:每次提…...
C语言指针(1)
目录 一、内存和地址 1、生活中的例子 2、内存的关系 二、指针变量和地址 1、&符号,%p占位符 2、一个简单的指针代码。 3、理解指针 4、解引用操作符 5、指针变量的大小。 三、指针变量类型的意义 1、指针解引用的作用 2、指针指针 3、指针-指针 4…...
C语言中的指针与数组
C语言中的指针与数组是编程中非常基础且强大的概念,它们之间有着紧密的联系和相互转换的可能性。深入理解这两个概念对于编写高效、可维护的C程序至关重要。以下将详细探讨C语言中的指针与数组,包括它们的基本概念、关系、应用以及一些高级话题。 一、指…...
CentOS7.9升级OpenSSL1.1.1w
下载 https://www.openssl.org/source/old/1.1.1/index.html 安装依赖 yum install gcc libffi-devel zlib* openssl-devel libffi-devel zlib-devel bzip2-devel openssl-devel ncurses-devel sqlite-devel readline-devel tk-devel gcc perl make 解压 tar -zxvf openss…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
