力扣题目101:对称二叉树
作者介绍：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, val=0, left=None, right=None):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)) |
| 优势 | 易于实现 | 不使用递归 | 不使用递归 |
| 劣势 | 可能栈溢出 | 空间开销大 | 空间开销大 |
应用示例
这些方法可以用于计算机视觉中对象的对称性检测，软件测试中的树结构数据验证，或者在机器学习数据预处理中检查数据的对称性。