【Leetcode】100 : 相同的树(Python)
2023-09-11 14:21:08 时间
题目:
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
题目解析:
方法一:
这个题目很明显就可以用递归来做,有关树的题目用递归来做基本上是我们需要想到的首选!如果两个树是相同的,我们只需要比较其树根是相同的,同时递归调用比较树根的下一级子树是相同的,那么则可以得到整个树的结构是相同的,我自己的方法如下:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if p==q==None: return True if q==None or p==None: return False if p.val==q.val: pleft=p.left pright=p.right qleft=q.left qright=q.right if self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right): return True
首先是设定递归的条件,然后在一级一级向下比较就可以了,思想和之前《剑指offer》当中的镜像二叉树的思想是相同的,后来发现自己第二步在进行递归的时候写多余了,没必要将树再往下推一步然后递归,可以直接进行递归,因此修改后如下:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if p==q==None: return True if q==None or p==None: return False if p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right): return True
这样两个if可以合并成一个if语句,减少了时间复杂度,同时也不需要再进行遍历到下一级之后再做递归,最后的成绩如下:
后来看了看其他人用java语言/go语言刷这道题的方法也基本这样,也就没必要再想迭代解法了。
相关文章
- python包
- python语法
- 安装python环境(win7 64bit)
- 【Python五篇慢慢弹(4)】模块异常谈python
- python code practice(二):KMP算法、二分搜索的实现、哈希表
- 猜年龄python实现
- Python 刷Leetcode题库,顺带学英语单词(6)
- Python 刷Leetcode题库,顺带学英语单词(39)
- Python 刷Leetcode题库,顺带学英语单词(20)
- Python 刷Leetcode题库,顺带学英语单词(17)
- Python编程:利用python编程实现对基于时间序列的数据(dataframe格式)按照指定时间范围进行单方向关联,不存在的日期补充为默认的NaN
- Python:利用python编程实现三维图像绘制展示(六面体旋转、三维球柱状体、下雪场景等)
- Python每日一练(数据分析篇)——第38天:分组聚合
- 已解决2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python (but this will use pure-Python parsing and wi
- 超级炫酷的3D旋转动态图——Python代码实现
- 来看看Python炫酷的颜色输出与进度条打印
- python快速读取非常大的文件
- Python图像处理参考文章
- python--函数
- python里使用正则表达式的嵌套可选模式
- python自动化测试学习-Python测试框架之unittest和pytest
- 【Leetcode刷题Python】55. 跳跃游戏
- 【Leetcode刷题Python】35. 搜索插入位置
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- python零基础学编程:Python是什么?为什么Python这么火,学Python能干什么?
- python工具方法 11 图像批量处理【灰度化、缩放、周边空白裁剪】