当前位置：首页 > news >正文

LeetCode 101. 对称二叉树：递归与迭代的完美结合

news 2026/5/12 16:44:41

LeetCode 101. 对称二叉树：递归与迭代的完美结合

问题描述

给定一个二叉树，检查它是否是镜像对称的。

示例 1：

输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3] 输出：false

算法原理

核心思路

对称二叉树的判断可以通过以下方法实现：

递归方法：判断左子树和右子树是否镜像对称。具体来说，需要判断：
- 左子树的左节点与右子树的右节点是否对称
- 左子树的右节点与右子树的左节点是否对称
迭代方法：使用队列来模拟递归过程，每次取出两个节点进行比较。

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点恰好被访问一次。
空间复杂度：
- 递归方法：O(h)，其中 h 是二叉树的高度。递归调用栈的深度最大为 h。
- 迭代方法：O(n)，最坏情况下，队列中最多同时存在 O(n) 个节点（例如，当二叉树是满二叉树时，最后一层的节点数约为 n/2）。

代码实现

递归方法

# Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True def is_mirror(left, right): # 如果两个节点都为空，返回 True if not left and not right: return True # 如果只有一个节点为空，返回 False if not left or not right: return False # 比较节点值，并递归比较子节点 return (left.val == right.val and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)) return is_mirror(root.left, root.right)

迭代方法

from collections import deque # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True # 初始化队列，将左右子节点入队 queue = deque([root.left, root.right]) while queue: # 取出两个节点进行比较 left = queue.popleft() right = queue.popleft() # 如果两个节点都为空，继续循环 if not left and not right: continue # 如果只有一个节点为空，返回 False if not left or not right: return False # 如果节点值不相等，返回 False if left.val != right.val: return False # 将左子树的左节点和右子树的右节点入队 queue.append(left.left) queue.append(right.right) # 将左子树的右节点和右子树的左节点入队 queue.append(left.right) queue.append(right.left) return True

代码解析

递归方法

边界处理：如果根节点为None，返回True。
辅助函数定义：定义一个is_mirror函数，用于判断两个子树是否镜像对称。
递归终止条件：
- 如果两个节点都为空，返回True。
- 如果只有一个节点为空，返回False。
递归比较：比较两个节点的值，并递归比较左子树的左节点与右子树的右节点，以及左子树的右节点与右子树的左节点。
调用辅助函数：调用is_mirror函数，判断根节点的左子树和右子树是否镜像对称。

迭代方法

边界处理：如果根节点为None，返回True。
初始化队列：创建一个队列，并将根节点的左右子节点入队。
遍历队列：
- 取出两个节点进行比较。
- 如果两个节点都为空，继续循环。
- 如果只有一个节点为空，返回False。
- 如果节点值不相等，返回False。
- 将左子树的左节点和右子树的右节点入队，将左子树的右节点和右子树的左节点入队。
返回结果：如果队列遍历完成，返回True。