当前位置:网站首页>LeetCode #101. 对称二叉树
LeetCode #101. 对称二叉树
2022-08-09 11:43:00 【张楚明ZCM】
方法一:递归
对称意味着整个二叉树的左右字数也是对称的。
那么将左子树的左节点与右子树的右节点比较,左子树的右节点与右子树的左节点比较,如果这样的结构下,每一个节点都相等,则该二叉树对称。中间只要有一个不相等,则一定不对称。
利用递归的方法,同步移动左右子树的指针,左子树左移时,右子树右移,反之亦然。每次检查两指针的值是否相等,全部相等则返回True,中间只要不等就返回False。
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.compare(root.left, root.right)
def compare(self, p: Optional[TreeNode], q:Optional[TreeNode]) -> bool:
if p == None and q == None:
return True
if p == None or q == None:
return False
if p.val != q.val:
return False
else:
return self.compare(p.left, q.right) and self.compare(p.right, q.left)
复杂度分析
时间复杂度:
空间复杂度:
完整测试代码
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.compare(root.left, root.right)
def compare(self, p: Optional[TreeNode], q:Optional[TreeNode]) -> bool:
if p == None and q == None:
return True
if p == None or q == None:
return False
if p.val != q.val:
return False
else:
return self.compare(p.left, q.right) and self.compare(p.right, q.left)
class main:
a = Solution()
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(2)
node4 = TreeNode(3)
node5 = TreeNode(4)
node6 = TreeNode(4)
node7 = TreeNode(3)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7
b = a.isSymmetric(node1)
print(b)
if __name__ == '__main__':
main()
方法二:迭代
先设置一个列表,将二叉树根节点root入队两次。每次从队列中提取两个结点进行比较,为空则跳过,不同则返回False。然后将下一层的结点加入比较。加入新一层的结点时注意将两个结点的左右子节点按照相反的顺序入队。
如此重复,中间只要有不相等就返回False,循环遍历完成都相等则返回True。
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
queue = [root, root]
while queue:
p, q = queue.pop(), queue.pop()
if not p and not q:
continue
if not p or not q:
return False
if p.val != q.val:
return False
queue.append(p.left)
queue.append(q.right)
queue.append(p.right)
queue.append(q.left)
return True
复杂度分析
时间复杂度:
空间复杂度:
边栏推荐
- fork creates multiple child processes
- Visual Studio 2017 ASP.NET Framework MVC 项目 MySQL 配置连接
- 【Robustness of VQA-1】——2019-EMNLP-Don’t Take the Easy Way Out
- C# async 和 await 理解
- TIC2000系列处理器在线升级
- matlab simulink的scope 示波器光标如何移动记录
- 获取url地址中问号后参数(即使是iframe也可以)
- x86 exception handling and interrupt mechanism (2) interrupt vector table
- TI的片上固化好的boot ROM(上电引导加载程序)退出后的去向
- JS封装防抖(代码持续优化)
猜你喜欢
enum in c language
How tall is the B+ tree of the MySQL index?
mysql8.0和navicat premium15下载安装
x86 exception handling and interrupt mechanism (2) interrupt vector table
TIC2000系列处理器在线升级
TI的片上固化好的boot ROM(上电引导加载程序)退出后的去向
Visual Studio 2017 ASP.NET Framework MVC 项目 MySQL 配置连接
Senior told me that the giant MySQL is through SSH connection
【Data augmentation in NLP】——1
实现strcat函数
随机推荐
OC-块对象
mysql8.0和navicat premium15下载安装
"Digital Economy Panorama White Paper" Special Analysis of Banking Industry Intelligent Marketing Application Released
Redis高可用部署
软件测试——金融测试类面试题,看完直接去面试了
TIC2000系列处理器在线升级
人体解析(Human Parse)开源数据集整理
结构体变量的首地址获取注意事项
web课程设计
MySQL事务隔离级别
web course design
es6Generator函数的异常处理
Fapi_StatusType Fapi_issueProgrammingCommand使用注意事项
Recommend a free 50-hour AI computing platform
湖南进芯电子替代TIC2000的可能性
【VQA survey】视觉问答中的语言学问题
学生成绩查找系统
在北京参加UI设计培训到底怎么样?
redis的缓存穿透、缓存雪崩、缓存击穿怎么搞?
PAT1013 并查集 DFS(查找联通分量的个数)