python每日一题【剑指 Offer 26. 树的子结构】

news/2024/3/28 17:11:43/文章来源:https://blog.csdn.net/qq_42896431/article/details/128106922

day23-2022.11.19

题目信息来源

作者:Krahets

链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm

来源:力扣(LeetCode)

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

 	 3/ \4   5/ \1   2

给定的树 B:

	4 /1

返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

输入:A = [1,2,3], B = [3,1]
输出:false输入:A = [3,4,5,1,2], B = [4,1]
输出:true

限制:0 <= 节点个数 <= 10000

题解:个人版,队列方法

可能是广度遍历的方法。我的代码可以看到有很多重复,结构相似的代码段,之后看看题解考虑一下怎么优化。现在先考虑能不能用递归的方式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if not B:return False       # 空树不是任何树的子结构# 考虑了一下,可能是三个队列,一个是A的所有节点队列遍历,一个是B的所有队列,一个是检查A的时候单独的队列aQueue = [A]check_sub = Falsewhile aQueue:# 检查a队列有无和b队列对上的aNode = aQueue.pop(0)# 如果对不上考虑下一个节点if aNode.left!=None:aQueue.append(aNode.left)if aNode.right!=None:aQueue.append(aNode.right)# 如果对上,就需要检查结构,遍历b的结构if aNode.val==B.val:# 初始化b的遍历结构和a对应的子结构aSub, bSub = [aNode], [B]while bSub:a_node, b_node = aSub.pop(0), bSub.pop(0)# 如果pop的值相等,则可以考虑看看树的下一层的情况if b_node.val==a_node.val:# left都不为空,暂时结构上是正确的if b_node.left!=None and a_node.left!=None:bSub.append(b_node.left)aSub.append(a_node.left)check_sub = True# b不为空,a为空结构上错误elif b_node.left!=None and a_node.left==None:check_sub = Falsebreak# a和b都为空,结构上是正确的。# 其实还有一种情况:b为空,a不为空,这个我也不知道怎么处理其实,但似乎测试里没有这种情况,或者就是Falseelif b_node.left==None:check_sub = Trueif b_node.right!=None and a_node.right!=None:bSub.append(b_node.right)aSub.append(a_node.right)check_sub = Trueelif b_node.right!=None and a_node.right==None:check_sub = Falsebreakelif b_node.right==None:check_sub = Trueelse:check_sub = Falsebreakreturn check_sub

题解:个人方法,递归版本

这个很像之前的【矩阵中的路径】那道题,就是数据结构变了一下,如果广度就要两层遍历,深度就需要一层遍历加递归。

这里官方题解的解释更清楚,为啥需要两层遍历:

链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dsbng/

若树 B 是树 A 的子结构,则子结构的根节点可能为树 A 的任意一个节点。因此,判断树 B 是否是树 A 的子结构,需完成以下两步工作:

  1. 先序遍历树 A 中的每个节点 nAn_AnA ;(对应函数 isSubStructure(A, B)
  2. 判断树 A 中 以 nAn_AnA 为根节点的子树 是否包含树 B 。(对应函数 recur(A, B)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if not B:return False       # 空树不是任何树的子结构# 递归参数:A和B的left或者right Node# 递归获得参数有多少种可能性,分别返回什么参数。首先希望传递的参数是出现子树可能性的时候的递归def checkSubTree(a_node, b_node):# 检查 aNode 的值和 bNode 的值是否相等if a_node==None and b_node!=None:return Falseelif b_node==None:return Trueif a_node.val!=b_node.val:return Falsereturn checkSubTree(a_node.left, b_node.left) and checkSubTree(a_node.right, b_node.right)aQueue = [A]while aQueue:# 检查a队列有无和b队列对上的aNode = aQueue.pop(0)# 如果对不上考虑下一个节点if aNode.left!=None:aQueue.append(aNode.left)if aNode.right!=None:aQueue.append(aNode.right)# 如果对上,就需要检查结构,遍历b的结构if aNode.val==B.val:check_sub = checkSubTree(aNode.right, B.right) and checkSubTree(aNode.left, B.left)           if check_sub==True:return Trueelse:continuereturn False

看到最后官方题解是基于递归版本,在第一层遍历部分,用来递归来解决。

链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dsbng/

返回值: 若树 B 是树 A 的子结构,则必满足以下三种情况之一,因此用或 || 连接;

  • 以 节点 A 为根节点的子树 包含树 B ,对应 recur(A, B)
  • 树 B 是 树 A 左子树 的子结构,对应 isSubStructure(A.left, B)
  • 树 B 是 树 A 右子树 的子结构,对应 isSubStructure(A.right, B)

可以尝试在我的基础上从这个思路上优化,但特殊情况我可能现在提前 return,需要注意的是,这里还要加入 not A ,中间是 or 连接。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if not B or not A:return False       # 空树不是任何树的子结构# 递归参数:A和B的left或者right Node# 递归获得参数有多少种可能性,分别返回什么参数。首先希望传递的参数是出现子树可能性的时候的递归def checkSubTree(a_node, b_node):# 检查 aNode 的值和 bNode 的值是否相等if a_node==None and b_node!=None:return Falseelif b_node==None:return Trueif a_node.val!=b_node.val:return Falsereturn checkSubTree(a_node.left, b_node.left) and checkSubTree(a_node.right, b_node.right)return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B) or checkSubTree(A, B)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_38895.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

遇到Bug漏测,不能总想着甩锅吧

背景 漏测Bug是指产品逻辑缺陷在测试过程中没有被发现&#xff08;尤其是测试环境可以重现的缺陷&#xff09;&#xff0c;上线版本发布后或者在用户使用体验后发现并反馈回来的缺陷。 漏测Bug可能造成线上故障或者资损&#xff0c;在对产品测试过程中&#xff0c;自己也难免…

品优购项目案例制作需要注意的内容笔记

个人在做的时候遇到的&#xff0c;自己觉得需要注意的内容 模块化 1.有些样式和结构在很多页面会出现&#xff0c;比如页面的头部和底部&#xff0c;大部分页面都有。此时可以把这些结构和样式单独作为一个模块&#xff0c;然后重复使用 2.这里最典型的应用就是common.css公…

Dubbo3入门实践,SpringBoot+Dubbo+Nacos+DubboAdmin

前言 学习Dubbo的过程中发现官网文章太过简单&#xff0c;而且没有提供完整的项目整合&#xff0c;导致入门门槛比较高&#xff0c;初学者不知从何下手。本文将在SpringBoot的基础上整合Dubbo&#xff0c;注册中心使用当下流行的Nacos&#xff0c;还将使用Dubbo-Admin来管理服务…

web前端-javascript-基本数据类型和引用数据类型(对象和基本数据类型保存到栈内存,对象保存在堆内存,比较两个基本数据类型或引用数据类型)

基本数据类型和引用数据类型 var a 123; var b a; a;/* console.log("a "a); console.log("b "b); */var obj new Object(); obj.new "孙悟空";var obj2 obj;//修改obj的name属性 obj.name "猪八戒";/* console.log(obj.name…

C. Strange Test(位运算或)

Problem - 1632C - Codeforces 伊戈尔正在读11年级。明天他将不得不写一份信息学测试&#xff0c;由学校最严格的老师帕维尔-杰尼索维奇负责。 伊戈尔知道测试将如何进行&#xff1a;首先&#xff0c;老师会给每个学生两个正整数a和b&#xff08;a<b&#xff09;。之后&…

BP神经网络详解,Python实现求解异或问题

BP神经网络 符号及其含义 nln_lnl​表示第lll层神经元的个数&#xff1b;f(⋅)f()f(⋅)表示神经元的激活函数&#xff1b;W(l)∈Rni∗ni−1W^{(l)}\in\mathbb R^{n_i*n_{i-1}}W(l)∈Rni​∗ni−1​表示第l−1l-1l−1层到第lll层的权重矩阵&#xff1b;wij(l)w_{ij}^{(l)}wij(l…

idea手动创建webapp(在main文件夹下)

SSM自学笔记 文章目录一、Maven使用正常情况首先不使用骨架创建好Maven项目然后选择Project Structure...选择要创建webapp的模块修改路径二、Maven不正常工作时一、Maven使用正常情况 首先不使用骨架创建好Maven项目 然后选择Project Structure… 选择要创建webapp的模块 选好…

python数据容器——列表

目录 一.数据容器 二.数据容器——列表 基本语法 注意 三.列表的下标&#xff08;索引&#xff09; 嵌套列表的下标&#xff08;索引&#xff09; 四.列表的常用操作&#xff08;方法&#xff09; 1.查询元素下标 2.插入元素 3.删除元素 4.统计元素 说明 一.数据容器 1&a…

传奇出现黑屏卡屏不动是怎么回事

在写这篇文章之前&#xff0c;先给给大家说一下&#xff0c;这篇文章写的是出现黑屏、卡屏不动是我们玩传奇的时候出现的&#xff0c;而不是在架设传奇时候出现的&#xff0c;所以要特别是注意一下&#xff0c;架设和玩出现黑屏是完全不一样的&#xff0c;所以解决方案也不一样…

H3C opsf/rip/ftp/telent/nat/acl综合

实验拓扑 拓扑下载 https://sharewh2.xuexi365.com/share/84b85b32-acb7-4f62-a389-6188680a19f3?t3 图 1-1 注&#xff1a;如无特别说明&#xff0c;描述中的 R1 或 SW1 对应拓扑中设备名称末尾数字为 1 的设备&#xff0c;R2 或 SW2 对应拓扑中设备名称末尾数字为 2 的设备…

【jmeter】windows下使用 (测试MQTT)

1. 添加线程组 二、添加如下请求 1. 添加创建连接请求-选中线程组&#xff0c; 点击右键&#xff0c;添加>取样器>MQTT Connect设置MQTT连接 本次使用本机开启的MQTT服务进行测试&#xff0c;默认ip为127.0.0.1&#xff0c;端口默认1883 2. 添加发布请求-选中线程组 …

软件测试之对于测试的反思及思考

1.针对一个页面&#xff0c;从页面的完整性(包括字段、输入框、功能点)出发 2.对于分页&#xff0c;考虑未在首页的时候的测试&#xff0c;末页的情况。 3.对条件的查询来说&#xff0c;要针对于单个输入框的测试、交叉输入框的测试 4.对于删除、修改等&#xff0c;要考虑你删除…

nablet Elements released处理视频的组件

nablet Elements released处理视频的组件 mediaEngine-一个转码工厂&#xff0c;为视频工作流从贡献到分发提供动力。 HeightScreen-AI驱动的工具&#xff0c;用于将视频转换为垂直屏幕&#xff0c;自动选择感兴趣的区域。 Shrynk-AI驱动的解决方案&#xff0c;可自动完成高亮编…

【站内题解】十六道csdn每日一练Python题解

文章目录题目一&#xff1a; 游乐园的门票1. 问题描述2. 输入描述3. 输出描述4. 示例4.1 输入4.2 输出5. 答案5.1 解法一5.2 解法二题目二&#xff1a;小桥流水人家1. 问题描述2. 输入描述3. 输出描述4. 示例4.1 输入4.2 输出5. 答案题目三&#xff1a;小艺读书1. 问题描述2. 输…

Wordpress模板主题中functions.php常用功能代码与常用插件(持续收集整理)

用Wordpress建站的初学者一定会需要用到的Wordpress模板主题中functions.php常用功能代码与常用插件。慢慢持续收集整理....... 目录 一、Wordpress模板主题中functions文件常用的代码 二、Wordpress自定义字段的设定与调用代码&#xff08;系统常规自定义字段&#xff09; …

ESP32基础应用之LVGL基础

文章目录1 实验目的1.1 参考文章2 实验工具3 准备工作3.1 搭建ESP32开发环境3.2 克隆lv_port_esp32工程4 配置lv_port_esp32工程5 实验验证6 使用过程遇到的问题6.1 触摸功能点击屏幕位置不对1 实验目的 本实验为使用ESP32实现LVGL&#xff08;轻量级的嵌入式图形库&#xff0…

消息队列概述与扩展

一、消息队列的特性 与业务解藕&#xff1a;一个具有普适性质的消息队列组件不需要考虑上层的业务模型&#xff0c;只做好消息的分发就可以了&#xff0c;上层业务的不同模块反而需要依赖消息队列所定义的规范进行通信。FIFO&#xff1a;先投递先到达的保证是一个消息队列和一…

计算机组成原理习题课第三章-2(唐朔飞)

计算机组成原理习题课第三章-2&#xff08;唐朔飞&#xff09; ✨欢迎关注&#x1f5b1;点赞&#x1f380;收藏⭐留言✒ &#x1f52e;本文由京与旧铺原创&#xff0c;csdn首发&#xff01; &#x1f618;系列专栏&#xff1a;java学习 &#x1f4bb;首发时间&#xff1a;&…

梦开始的地方——C语言柔性数组

文章目录柔性数组什么是柔性数组&#xff1f;柔性数组的使用柔性数组的优点柔性数组 什么是柔性数组&#xff1f; 在C99中&#xff0c;结构体最后一个元素它允许是一个未知大小的数组&#xff0c;这就叫做柔性数组成员。 这个概念听起来可能有点不可以思议&#xff0c;但它的…

第三十九篇 自定义指令 - directive

前面讲了关于在Vue中如何来进行封装swiper组件的内容&#xff0c;本篇内容讲到使自定义组件&#xff0c;讲这块内容也是同样为了后续再次回顾封装swiper组件变化做铺垫内容&#xff0c;那么什么是自定义指令&#xff0c;在前面的内容讲过了好些常用的指令&#xff0c;如 v-modl…