Python3解leetcode Subtree of Another Tree
2024-10-07 11:17:19
问题描述:
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
解题思路:
关于树的题目,第一反应就是利用DFS解答,此题也不例外。
代码:
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
def dfs(a,b):
if not a or not b: #若果a,b中存在null,处理手段
return not a and not b
#以下处理时在a,b皆不为null的情况下进行讨论
if a.val==b.val and dfs(a.left,b.left) and dfs(a.right,b.right):
return True
if b is t:#当b时t的时候,判断a的左右子树分别与t是否相等
return dfs(a.left,t) or dfs(a.right,t) return False return dfs(s,t)
第4、5行代码,将各种子树为空的情形缩略到一个条件判断中,精简了代码。
第7、8行代码,判断当前树是否和t树完全相同
第9、10行代码,只有当b是t的时候才生效,意思是如果该次执行是从第二个if递归过来的,那么就不进行判断,因为该次执行判断是当前树的子树与t的子树是否相同,并非是判断t是否与当前树相同。
最后12行代码,直接返回False即可。但如果返回的是dfs(a,t),代码执行时间会缩短75%,但是我没懂为何会缩短如此之多。
最新文章
- 第2月第5天 arc invocation getReturnValue
- Spring Application Event Example
- MongoDB官网驱动仓库封装
- Auto Mapper03
- IO-同步,异步,阻塞,非阻塞
- Unity3D Shader入门指南(二)
- EntityFramework中Mapper怎么定义联合主键?
- Windows环境自动获取AWR报告
- poj3278 BFS入门
- Android学习手记(1) Activity跳转
- android View各属性详解
- CASE WHEN用法
- Django--入门篇:下载与项目生成
- python中利用上下文管理器来实现mysql数据库的封装
- maven(四):一个基本maven项目的pom.xml配置
- rem 布局的闪现问题
- MT【178】平移不变性
- Leetcode: Binary Tree Postorder Transversal
- dubbo注册中心zookeeper出现异常 Opening socket connection to server 10.70.42.99/10.70.42.99:2181. Will not attempt to authenticate using SASL (无法定位登录配置)
- 移动端h5列表页上拉加载更多
热门文章
- 负载均衡环境搭建(nginx和tomcat)
- 模拟鼠标向下滚动 http://bbs.2ccc.com/topic.asp?topicid=461769
- struts2 基础5 OGNL、标签、四大域、默认拦截器说明
- python程序的模块与包
- Whatever happens tomorrow, we've had today
- 浅谈Vue中的$set的使用
- ubuntu彩色图形界面
- jmeter _Random函数生成随机数
- Oracle数据库的下载与安装
- luogu 3426题解 (KMP)