力扣题目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

---

方法一：递归判断

解题步骤

1. 基本情况：如果两个节点都是 None，返回 True；一个是 None 另一个不是，返回 False。
2. 比较节点：比较当前两节点的值，如果不相等，返回 False。
3. 递归比较：递归比较左子树的左孩子和右子树的右孩子，以及左子树的右孩子和右子树的左孩子。

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) 是树的高度，空间消耗来自递归的栈空间。

方法二：迭代使用队列

解题步骤

1. 初始化队列：将根节点的两份加入队列。
2. 迭代比较：每次从队列中取出两个节点并比较它们。
3. 子节点入队：如果节点相同，则将它们的子节点按对称顺序加入队列。

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))，在最坏的情况下，队列中需要存储所有节点。

方法三：使用栈进行迭代

解题步骤

1. 使用栈：将根节点的两份压入栈中。
2. 迭代比较：从栈中弹出两个节点并进行比较。
3. 子节点压栈：如果节点相同，则将它们的子节点按对称顺序压入栈中。

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))
优势	易于实现	不使用递归	不使用递归
劣势	可能栈溢出	空间开销大	空间开销大

应用示例

这些方法可以用于计算机视觉中对象的对称性检测，软件测试中的树结构数据验证，或者在机器学习数据预处理中检查数据的对称性。