当前位置:网站首页>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
复杂度分析
时间复杂度:
空间复杂度:
边栏推荐
猜你喜欢
随机推荐
proto3-2 syntax
x86 Exception Handling and Interrupt Mechanism (1) Overview of the source and handling of interrupts
从零开始Blazor Server(9)--修改Layout
字节秋招二面把我干懵了,问我SYN报文什么情况下会被丢弃?
PAT1011
ClickHouse之MaterializeMySQL引擎(十)
【DB运营管理/开发解决方案】上海道宁为您提供提高工作便利性的集成开发工具——Orange
[现代控制理论]6_稳定性_李雅普诺夫_Lyapunov
mysql参数学习----max_allowed_packet
TI的片上固化好的boot ROM(上电引导加载程序)退出后的去向
Senior told me that the giant MySQL is through SSH connection
修改VOT2018.json文件,去掉图片路径中的color
WPF implements a MessageBox message prompt box with a mask
Two ways to enter the Oracle database
推荐一个免费50时长的AI算力平台
Visual Studio 2017 ASP.NET Framework MVC 项目 MySQL 配置连接
Redis的下载安装
TIC2000调用API函数Flash擦除片上FLASH失败
ThreadLocal类
redis内存的淘汰机制