【Leetcode刷题Python】剑指 Offer 26. 树的子结构
2023-09-14 09:13:02 时间
1 题目
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B:
4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2 解析
(1)首先如果两个子树都为空,不成立
(2)判断A的左子树和B是否为包含关系,或者A的右子树是否为包含关系,或者递归去找所有子树是否包含了,只要有一个返回True即可。
3 python实现
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def recur(A,B):
if not B:
return True
if not A or A.val !=B.val:
return False
return recur(A.left,B.left) and recur(A.right,B.right)
if not A or not B:
return False
return recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
相关文章
- Python虚拟环境的安装和配置-virtualenv与windows下多个python版本共存
- python中日志logging模块的性能及多进程详解
- python 必选参数、默认参数、可变参数和、关键字参数
- python: easyocr的安装和使用(easyocr 1.6.2 / Python 3.7.15 )
- 华为OD机试 - 回文字符串(Java & JS & Python)
- Python编程:利用python编程实现对基于时间序列的数据(dataframe格式)按照指定时间范围进行单方向关联,不存在的日期补充为默认的NaN
- Python语言学习之双下划线那些事:python和双下划线使用方法之详细攻略
- 已解决2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python (but this will use pure-Python parsing and wi
- python列表详解
- 【LeetCode Python实现】剑指 Offer II 038. 每日温度(中等)单调栈
- Python编程:安装python环境以及virtualenv虚拟环境
- 【leetcode】Word Break(python)
- python基础===Python 迭代器模块 itertools 简介
- python基础===八大排序算法的 Python 实现
- 自己写的Python数据库连接类和sql语句拼接方法
- 【Leetcode刷题Python】11. 盛最多水的容器
- 【Leetcode刷题Python】子数组查找
- 【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
- Python前景如何?学会Python工作好找吗?
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- python零基础学编程:Python是什么?为什么Python这么火,学Python能干什么?
- Python爬虫自学系列(番外篇一):代理IP池