湖南网站建设公司,浙江嵊州最新消息,梵讯企业网站建设,网站验证码原理算法#xff1a;
其实就是比较左右子树是否可以翻转
比较的时候#xff1a;
比较外面的节点是否相等#xff0c;如示例1中的节点3
比较里面的节点是否相等#xff0c;如示例1中的节点4
基本思路是这样的#xff0c;那怎么遍历呢#xff1f;
二叉树的题一定要掌握到…
算法
其实就是比较左右子树是否可以翻转
比较的时候
比较外面的节点是否相等如示例1中的节点3
比较里面的节点是否相等如示例1中的节点4
基本思路是这样的那怎么遍历呢
二叉树的题一定要掌握到底用哪种遍历来解决题目这样才能理解得更深刻
这道题一定是后序遍历
因为我们要搜集孩子信息返回上一层比如
左子树我们要搜集3L 4R的信息返回给2
右子树我们要搜集3R 4L的信息返回给2
这样才能比较2.left和2.right是否对称
调试过程
递归法 原因compare函数的定义不对我定义的输入一个节点但实际调用的是两个指针。
compare函数定义时的输入应该是两个子树,left和right
修改后还是报错了发现是对空树的理解不对空树被认为是对称的而我以为不对称改过来就好了。
正确代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def isSymmetric(self, root: Optional[TreeNode]) - bool:if root None:return Trueelse:res self.compare(root.left, root.right)return res
#定义一个compare函数用来比较左右子树
#具体比较就是外面的和外面的比里面的和里面的比def compare(self, left, right) - bool:#排除一些绝对不对称的情况if left None and right ! None:return Falseif right None and left ! None:return Falseif right None and left None:return Trueif right and left:outside self.compare(left.left,right.right)inside self.compare(left.right,right.left)issame outside and insidereturn issame
时间空间复杂度
时间复杂度isSymmetric函数会递归调用compare函数。在compare函数中我们比较给定二叉树的左子树和右子树。由于每个节点只访问一次时间复杂度为O(n)其中n是二叉树中的节点数。
空间复杂度 空间复杂度取决于递归栈的最大深度。在最坏的情况下当二叉树是倾斜的且高度为n时空间复杂度为O(n)。这是因为在任何时刻递归栈最多可以容纳n个函数调用。
总体而言时间复杂度为O(n)空间复杂度在最坏情况下为O(n)。
