国家图书馆网站建设介绍,做网站都要买服务器吗,北京网站制作服务,平面设计主要用的软件作者介绍#xff1a;10年大厂数据\经营分析经验#xff0c;现任大厂数据部门负责人。 会一些的技术#xff1a;数据分析、算法、SQL、大数据相关、python 欢迎加入社区#xff1a;码上找工作 作者专栏每日更新#xff1a; LeetCode解锁1000题: 打怪升级之旅 python数据分析… 作者介绍10年大厂数据\经营分析经验现任大厂数据部门负责人。 会一些的技术数据分析、算法、SQL、大数据相关、python 欢迎加入社区码上找工作 作者专栏每日更新 LeetCode解锁1000题: 打怪升级之旅 python数据分析可视化企业实战案例 python源码解读 程序员必备的数学知识与应用 备注说明方便大家阅读统一使用python带必要注释公众号 数据分析螺丝钉 一起打怪升级 题目描述
给定一个二叉树检查它是否是镜像对称的。
输入格式
root二叉树的根节点。
输出格式
返回布尔值表示树是否对称。
示例
示例 1
输入root [1,2,2,3,4,4,3] 输出True
示例 2
输入root [1,2,2,null,3,null,3] 输出False 方法一递归判断
解题步骤
基本情况如果两个节点都是 None返回 True一个是 None 另一个不是返回 False。比较节点比较当前两节点的值如果不相等返回 False。递归比较递归比较左子树的左孩子和右子树的右孩子以及左子树的右孩子和右子树的左孩子。
Python 示例
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef isSymmetric(root):判断二叉树是否对称:param root: TreeNode, 二叉树的根节点:return: bool, 是否对称def isMirror(left, right):if not left and not right:return Trueif not left or not right:return Falsereturn left.val right.val and isMirror(left.left, right.right) and isMirror(left.right, right.left)return isMirror(root, root)# 示例调用
root TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
print(isSymmetric(root)) # 输出: True算法分析
时间复杂度(O(n))其中 (n) 是树中节点的数量因为需要访问树中的每一个节点。空间复杂度(O(h))其中 (h) 是树的高度空间消耗来自递归的栈空间。
方法二迭代使用队列
解题步骤
初始化队列将根节点的两份加入队列。迭代比较每次从队列中取出两个节点并比较它们。子节点入队如果节点相同则将它们的子节点按对称顺序加入队列。
Python 示例
from collections import dequedef isSymmetric(root):使用队列迭代判断二叉树是否对称:param root: TreeNode, 二叉树的根节点:return: bool, 是否对称queue deque([root, root])while queue:t1, t2 queue.popleft(), queue.popleft()if not t1 and not t2:continueif not t1 or not t2 or t1.val ! t2.val:return Falsequeue.append(t1.left)queue.append(t2.right)queue.append(t1.right)queue.append(t2.left)return True# 示例调用
root TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root)) # 输出: False算法分析
时间复杂度(O(n))因为需要访问每个节点。空间复杂度(O(n))在最坏的情况下队列中需要存储所有节点。
方法三使用栈进行迭代
解题步骤
使用栈将根节点的两份压入栈中。迭代比较从栈中弹出两个节点并进行比较。子节点压栈如果节点相同则将它们的子节点按对称顺序压入栈中。
Python 示例
def isSymmetric(root):使用栈迭代判断二叉树是否对称:param root: TreeNode, 二叉树的根节点:return: bool, 是否对称if not root:return Truestack [(root.left, root.right)]while stack:left, right stack.pop()if not left and not right:continueif not left or not right or left.val ! right.val:return Falsestack.append((left.left, right.right))stack.append((left.right, right.left))return True# 示例调用
root TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root)) # 输出: False算法分析
时间复杂度(O(n))需要访问每个节点。空间复杂度(O(n))在最坏的情况下栈中需要存储所有节点。
不同算法的优劣势对比
特征方法一递归方法二迭代队列方法三迭代栈时间复杂度(O(n))(O(n))(O(n))空间复杂度(O(h))(O(n))(O(n))优势易于实现不使用递归不使用递归劣势可能栈溢出空间开销大空间开销大
应用示例
这些方法可以用于计算机视觉中对象的对称性检测软件测试中的树结构数据验证或者在机器学习数据预处理中检查数据的对称性。
