当前位置: 首页 > news >正文

[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. 题目来源 链接&#xff1a;572. 另一棵树的子树 2. 题目解析 看到这个题目就感觉不简单&#xff0c;因为写了写 dfs 版本的&#xff0c;发现好像不太会… 还是简单粗暴一点&#xff0c;直接搞一个 前序中序&#xff0c;进行判断即可。我…...

C# 设计模式之简单工厂模式

总目录 前言 本文是个人基于C#学习设计模式总结的学习笔记&#xff0c;希望对你有用&#xff01; 1 基本介绍 简单工厂模式 定义&#xff1a;用于创建对象&#xff0c;将对象的创建与使用分离。 简单工厂模式中用于创建实例的方法是静态(static)方法&#xff0c;因而简单工厂…...

mac中dyld[5999]: Library not loaded: libssl.3.dylib解决方法

需要重新安装下openssl3.0版本 brew reinstall openssl3.0 安装后执行还是报错&#xff0c;需要找到openssl的安装路径 /opt/homebrew/Cellar/openssl3.0/3.0.14/lib/ 将libssl.3.dylib和libcrypto.3.dylib拷贝到自己的二进制文件同目录下&#xff0c;再执行二进制文件就可…...

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文件中引入子组件&#xff1a; "usingComponents": {"articleList":"../../components/articleList/articleList",}2.在父组件中给子组件绑定数据 <articleList num"{{number}}"></articleList>3.子组…...

【Python 逆向滑块】(实战五)逆向滑块,并实现用Python+Node.js 生成滑块、识别滑块、验证滑块、发送短信

逆向日期&#xff1a;2024.08.03 使用工具&#xff1a;Python&#xff0c;Node.js 本章知识&#xff1a;滑块距离识别&#xff0c;滑块轨迹生成&#xff0c;验证滑块并获取【validate】参数 文章难度&#xff1a;中等&#xff08;没耐心的请离开&#xff09; 文章全程已做去敏处…...

微服务架构设计的最佳实践

在当今快速变化的软件开发环境中&#xff0c;微服务架构因其灵活性、可扩展性和可维护性而逐渐成为大型分布式系统的首选架构模式。然而&#xff0c;成功实施微服务架构并非易事&#xff0c;它要求开发团队遵循一系列最佳实践来确保系统的可靠性、效率和可管理性。本文将探讨微…...

样式与特效(3)——实现一个测算页面

这次我们使用前端实现一个简单的游戏页面,理论上可以增加很多玩法&#xff0c;&#xff0c;但是这里为了加深前端的样式和JS点击事件&#xff0c;用该案例做练习。 首先需要掌握手机端的自适应&#xff0c;我们是只做手机端玩家页面 。需要允许自适应手机端页面&#xff0c; 用…...

芯片制造过程4光刻机

以下内容均取自哔哩哔哩up主谈三圈 链接: 芯片制造详解04&#xff1a;光刻技术与基本流程&#xff5c;国产之路不容易 1.光刻原理 通过光掩膜、光刻机、光刻胶进行光刻 光掩膜是芯片的蓝图&#xff0c;是一张刻有集成电路板图的玻璃遮光板光刻机就像一台纳米级的打印机&#…...

Nexus3 Repository代理pypi设置与应用

目录 1. 创建Blob库并指定路径 2. 创建pypi阿里镜像源 3. 创建pypi腾讯镜像源 4. 创建一个pypi组管理 5. 配置pip 6. 下载测试 扩展&#xff1a;配置好后无法下载解决思路。 Nexus 存储库中的 Blob 存储是指一种用于存储大量非结构化数据的技术。在 Nexus 存储库的上下文…...

PMP–知识卡片--燃起图

燃起图用两条曲线分别绘制随时间的推移、完成的工作量和总工作量的变化情况。它不仅能清晰地展示项目进度&#xff0c;还是对团队成员的一种激励形式。 使用燃起图可以更好地了解进度、范围变更和预期完成时间&#xff0c;它为所有相关方提供了更清晰的进度状态。 燃起图根据工…...

63 epoll服务器 (ET模式)

基于LT模式修改&#xff0c;并加入前面的应用层计算器&#xff0c;实现稍完整的服务器功能 1.修改tcp_socket.hpp&#xff0c;新增非阻塞读和非阻塞写接口 2.对于accept返回的new_sock加上EPOLLET这样的选项 注意&#xff1a;此代码暂时未考虑listen_sock ET的情况&#xff0c…...

AI Agent

一&#xff0c;什么是AI Agent&#xff1f; AI Agent&#xff08;人工智能代理&#xff09;是一种能够自主执行任务和决策的智能系统。它通常具备感知环境、处理信息和采取行动的能力&#xff0c;能够模拟人类的思维和行为方式。 它可以是软件程序&#xff0c;也可以是嵌入式…...

select

select函数简介: select是Linux中常用的多路复用IO机制&#xff0c;它允许程序同时监控多个文件描述符&#xff08;可以是套接字socket&#xff0c;也可以是普通文件&#xff09;的读、写和异常事件。 #include <sys/select.h> #include <sys/time.h> …...

按照指定格式打印pprint()

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 按照指定格式打印 pprint() [太阳]选择题 根据给定的Python代码&#xff0c;哪个选项是正确的&#xff1f; 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.理解分支 感性理解&#xff1a;分支可以理解为平行宇宙&#xff0c;但是在用户需要的时候&#xff0c;可以将两个平行宇宙合并&#xff0c;此时两个平行宇宙的效果将会"叠加"理性理解&#xff1a;每次提…...

C语言指针(1)

目录 一、内存和地址 1、生活中的例子 2、内存的关系 二、指针变量和地址 1、&符号&#xff0c;%p占位符 2、一个简单的指针代码。 3、理解指针 4、解引用操作符 5、指针变量的大小。 三、指针变量类型的意义 1、指针解引用的作用 2、指针指针 3、指针-指针 4…...

C语言中的指针与数组

C语言中的指针与数组是编程中非常基础且强大的概念&#xff0c;它们之间有着紧密的联系和相互转换的可能性。深入理解这两个概念对于编写高效、可维护的C程序至关重要。以下将详细探讨C语言中的指针与数组&#xff0c;包括它们的基本概念、关系、应用以及一些高级话题。 一、指…...

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…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

鸿蒙Navigation路由导航-基本使用介绍

1. Navigation介绍 Navigation组件是路由导航的根视图容器&#xff0c;一般作为Page页面的根容器使用&#xff0c;其内部默认包含了标题栏、内容区和工具栏&#xff0c;其中内容区默认首页显示导航内容&#xff08;Navigation的子组件&#xff09;或非首页显示&#xff08;Nav…...

MySQL基本操作(续)

第3章&#xff1a;MySQL基本操作&#xff08;续&#xff09; 3.3 表操作 表是关系型数据库中存储数据的基本结构&#xff0c;由行和列组成。在MySQL中&#xff0c;表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...