作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、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 = val self.left = left self.right = right def isSymmetric(root): """ 判断二叉树是否对称 :param root: TreeNode, 二叉树的根节点 :return: bool, 是否对称 """ def isMirror(left, right): if not left and not right: return True if not left or not right: return False return 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 deque def 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: continue if not t1 or not t2 or t1.val != t2.val: return False queue.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 True stack = [(root.left, root.right)] while stack: left, right = stack.pop() if not left and not right: continue if not left or not right or left.val != right.val: return False stack.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)) |
| 优势 | 易于实现 | 不使用递归 | 不使用递归 |
| 劣势 | 可能栈溢出 | 空间开销大 | 空间开销大 |
应用示例
这些方法可以用于计算机视觉中对象的对称性检测，软件测试中的树结构数据验证，或者在机器学习数据预处理中检查数据的对称性。
欢迎关注微信公众号 数据分析螺丝钉
