LeetCode 101. 对称二叉树 详细技术解析题目概述Problem Statement给定一棵二叉树的根节点 root判断这棵二叉树是否是轴对称的即二叉树沿中轴线对折后左右两部分能够完全重合返回布尔值true 表示对称false 表示不对称。核心规则对称逻辑二叉树的左子树和右子树需满足「镜像对称」即左子树的左节点与右子树的右节点对应相等左子树的右节点与右子树的左节点对应相等递归验证所有对应节点边界情况若树中仅含根节点无左右子树则为对称若左右子树有一个为空、另一个不为空则不对称进阶要求需实现递归和迭代两种解法兼顾代码简洁性与工业级稳定性。示例提示示例1输入 root [1,2,2,3,4,4,3] → 输出 true解释根节点1的左子树为2左3、右4右子树为2左4、右3左子树与右子树镜像对称整体二叉树轴对称。示例2输入 root [1,2,2,null,3,null,3] → 输出 false解释根节点1的左子树为2右3右子树为2右3左子树的右节点3与右子树的左节点null不相等因此不对称。问题分析Problem Analysis核心难点镜像判断逻辑需明确「镜像对称」的核心是「两个节点的对应关系」而非单个子树的对称避免误判为“左子树对称、右子树对称即整体对称”节点对应关系需同时验证两个节点的值相等且一个节点的左孩子与另一个节点的右孩子、一个节点的右孩子与另一个节点的左孩子分别对称边界处理空节点的判断的是关键需区分“两个节点都为空”对称和“一个为空、一个不为空”不对称的场景迭代解法的设计需用队列/栈模拟递归的节点对比流程确保所有对应节点都能被逐一验证。关键思路对称二叉树的核心是「根节点的左右子树镜像对称」可拆解为“验证两个节点是否镜像”的子问题两种解法均围绕该子问题展开递归思路推荐入门代码简洁核心子问题设计辅助函数接收两个节点判断这两个节点是否镜像对称终止条件① 两个节点都为空 → 对称返回true② 一个为空、一个不为空 → 不对称返回false③ 两个节点值不相等 → 不对称返回false递归逻辑递归验证“第一个节点的左孩子与第二个节点的右孩子”“第一个节点的右孩子与第二个节点的左孩子”两者都对称才返回true主函数逻辑若根节点为空本题节点数≥1可省略返回true否则调用辅助函数验证根节点的左、右子树是否镜像。迭代思路工业级常用避免递归栈溢出核心逻辑用队列或栈存储需要对比的「节点对」模拟递归的验证顺序初始化将根节点的左、右子树作为第一对节点加入队列循环处理每次取出队列中的两个节点按终止条件判断是否对称若对称将“第一个节点的左孩子与第二个节点的右孩子”“第一个节点的右孩子与第二个节点的左孩子”加入队列继续验证终止条件队列为空所有节点对验证完毕返回true或出现不对称节点对返回false。技术选型与优化点数据结构递归无需额外数据结构迭代使用队列FIFO符合层序对比逻辑或栈LIFO符合前序对比逻辑推荐队列更直观遍历方式递归基于深度优先遍历DFS迭代基于广度优先遍历BFS两种方式均能覆盖所有节点对时间复杂度O(n)n为二叉树节点数每个节点仅被访问和对比一次无冗余操作空间复杂度递归为O(h)h为树的高度最坏情况为链表hn迭代为O(n)队列最多存储一层的节点对最坏情况为满二叉树的最后一层节点数≈n/2优化点迭代版使用collections.deque实现队列确保节点取出操作的时间复杂度为O(1)递归版可直接内嵌辅助函数无需额外定义简化代码。完整代码实现Python严格贴合题目要求的代码格式提供「递归版」简洁易懂和「迭代版」稳定无栈溢出两种实现均包含详细注释可直接复制提交版本1递归版推荐入门简洁高效fromtypingimportOptional# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:defisSymmetric(self,root:Optional[TreeNode])-bool:# 辅助函数判断两个节点是否镜像对称defis_mirror(node1:Optional[TreeNode],node2:Optional[TreeNode])-bool:# 终止条件1两个节点都为空对称ifnotnode1andnotnode2:returnTrue# 终止条件2一个为空、一个不为空不对称ifnotnode1ornotnode2:returnFalse# 终止条件3两个节点值不相等不对称ifnode1.val!node2.val:returnFalse# 递归验证node1的左 ↔ node2的右node1的右 ↔ node2的左returnis_mirror(node1.left,node2.right)andis_mirror(node1.right,node2.left)# 主逻辑根节点为空本题节点数≥1可省略或左右子树镜像对称returnis_mirror(root.left,root.right)版本2迭代版BFS工业级稳定fromtypingimportOptionalfromcollectionsimportdeque# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:defisSymmetric(self,root:Optional[TreeNode])-bool:# 边界条件根节点为空本题节点数≥1可省略ifnotroot:returnTrue# 初始化队列存入需要对比的节点对根节点的左右子树queuedeque()queue.append(root.left)queue.append(root.right)# 循环处理所有节点对whilequeue:# 每次取出两个节点一对需要对比的节点node1queue.popleft()node2queue.popleft()# 情况1两个节点都为空继续验证下一对ifnotnode1andnotnode2:continue# 情况2一个为空、一个不为空或值不相等直接返回falseifnotnode1ornotnode2ornode1.val!node2.val:returnFalse# 加入下一对需要对比的节点node1左 ↔ node2右node1右 ↔ node2左queue.append(node1.left)queue.append(node2.right)queue.append(node1.right)queue.append(node2.left)# 所有节点对验证完毕均对称returnTrue代码解析Code Explanation1. 递归版代码解析辅助函数is_mirror核心是验证两个节点是否镜像包含3个终止条件覆盖所有边界场景避免空指针异常递归逻辑is_mirror(node1.left, node2.right) and is_mirror(node1.right, node2.left)确保两个节点的对应子节点也满足镜像关系只有两者都为true当前节点对才对称主函数逻辑直接调用辅助函数验证根节点的左、右子树是否镜像无需额外处理根节点根节点无对称节点只需验证其子树优势代码简洁逻辑清晰符合人类思维习惯适合面试快速编写。2. 迭代版代码解析队列初始化将根节点的左、右子树作为第一对节点加入队列开启对比流程循环处理每次取出两个节点先判断是否都为空若为空继续下一对若一空一非空直接返回false若两个节点都非空判断值是否相等不相等则返回false将下一对需要对比的节点加入队列node1左与node2右、node1右与node2左确保后续验证的连贯性终止逻辑队列为空时说明所有节点对都验证完毕返回true若过程中出现不对称场景直接返回false提前终止提升效率优势无递归栈溢出风险适合节点数较多的场景本题节点数≤1000递归也可但工业级更推荐迭代。3. 边界情况处理重点仅根节点root.left和root.right都为空递归版中is_mirror(null, null)返回true迭代版队列取出两个nullcontinue后队列空返回true符合预期左右子树一空一非空如root.leftnullroot.right2递归版返回false迭代版取出null和2直接返回false节点值相等但子树不对称如示例2根节点左右子树值都是2但左子树右节点是3右子树右节点是3左子树左节点是null右子树左节点是null验证时node1.leftnull与node2.right3一空一非空返回false满二叉树对称如示例1所有节点对都满足镜像关系递归/迭代均会验证所有节点最终返回true。测试案例验证Test Case Verification示例1对称满二叉树验证# 输入root [1,2,2,3,4,4,3]二叉树结构# 1# / \# 2 2# / \ / \# 3 4 4 3# 执行递归版流程1.调用is_mirror(2,2)两个节点值相等继续递归2.调用is_mirror(3,3)node1左3node2右3值相等继续递归3.is_mirror(3.leftnull,3.rightnull)→ trueis_mirror(3.rightnull,3.leftnull)→ true因此3和3对称4.调用is_mirror(4,4)node1右4node2左4值相等递归后也对称5.因此2和2对称整体返回true# 输出true与示例一致示例2不对称二叉树验证# 输入root [1,2,2,null,3,null,3]二叉树结构# 1# / \# 2 2# \ \# 3 3# 执行迭代版流程1.队列初始化[2,2]2.取出2和2值相等加入下一对节点2.left(null)、2.right(3)、2.right(3)、2.left(null)3.取出null和3一空一非空直接返回false# 输出false与示例一致边界案例仅根节点# 输入root [1]仅根节点左右子树都为空# 递归版is_mirror(null, null) → true# 迭代版队列初始化[null, null]取出后continue队列空返回true# 输出true性能分析Performance Analysis时间复杂度两种版本均为O(n)n为二叉树节点数。每个节点仅被访问1次对比操作是O(1)无冗余计算效率极高完全满足题目节点数≤1000的要求空间复杂度递归版O(h)h为树的高度。最好情况完全二叉树hlog₂n最坏情况链表本题不可能因链表无法对称hn迭代版O(n)队列最多存储一层的节点对最坏情况为满二叉树的最后一层节点对数为n/2空间开销稳定。对比递归版代码更简洁适合面试迭代版更稳定适合大规模二叉树实际项目中可根据场景选择。常见错误与避坑指南Common Mistakes误判对称逻辑认为“左子树对称、右子树对称即整体对称”忽略镜像关系如左子树是[2,3,4]右子树是[2,4,3]单独看都对称但整体镜像对称若右子树是[2,3,4]则不对称边界条件遗漏未判断“两个节点都为空”的场景导致递归无限调用或迭代队列无限循环空指针异常未判断节点为空就访问node.val如当node1为空、node2非空时直接判断node1.val ! node2.val会报空指针错误迭代版队列操作错误加入节点对时顺序错误如加入node1.left和node1.right、node2.left和node2.right导致对比对象错误递归辅助函数设计错误辅助函数仅接收一个节点试图判断单个子树是否对称而非两个节点是否镜像逻辑完全错误。总结Summary本题是二叉树镜像判断的经典题目核心是理解「镜像对称」的本质——“两个节点的对应子节点相互对称”而非单个子树的对称。递归和迭代两种解法均围绕这一核心前者简洁、后者稳定适合不同场景。核心收获掌握二叉树镜像判断的核心逻辑学会将复杂问题拆解为“两个节点是否镜像”的子问题熟练实现递归和迭代两种解法理解两者的底层逻辑和适用场景强化二叉树边界处理能力避免空指针异常精准覆盖所有对称/不对称场景。本题难度简单到中等适合巩固二叉树遍历和递归/迭代思路其核心逻辑可迁移到其他二叉树题目如判断两棵树是否镜像、翻转二叉树后判断是否与原树对称等是二叉树学习的重要基础。扩展思考Extension如何判断两棵二叉树是否互为镜像提示类比本题递归/迭代思路同时遍历两棵树验证对应节点是否镜像若二叉树节点值可重复如何优化判断逻辑提示无需额外优化核心仍为节点值相等子节点镜像重复值不影响判断如何修复一棵不对称的二叉树使其成为对称二叉树提示基于镜像逻辑补充缺失节点或修改节点值使左右子树镜像。