力扣热题100里101. 对称二叉树是一道绕不开的基础题。很多人第一次做它觉得比反转二叉树难一点比前序中序后序的遍历又简单一点但真要动手写却经常在递归函数的入参和边界条件上栽跟头。这道题本质上考的是“镜像对应”这个概念和“判断两棵树是否相同”有细微差别反而成了面试官最爱埋雷的地方。无论是准备秋招春招还是单纯想巩固二叉树递归、迭代遍历的基本功这道题都值得认真吃透。下面我把自己的解题过程、踩过的坑、以及不同写法之间的优劣整理出来给刷题的你做一个可以直接照抄的参考。1. 题目理解与核心思路拆解1.1 题目描述到底在问什么力扣101的题目很短给你一个二叉树的根节点 root检查它是否轴对称。对称二叉树也叫镜像二叉树意思是以根节点为中心线整棵树左右两边完全镜像。比如根节点只有一个那这棵树天然对称如果根节点有左孩子和右孩子那么左孩子的值要等于右孩子的值同时左孩子的左子树要镜像等于右孩子的右子树左孩子的右子树要镜像等于右孩子的左子树。这里有个特别容易搞混的点它和“判断两棵树完全相同”不是一回事。判断相同树是左孩子对应左孩子右孩子对应右孩子而对称二叉树是左孩子的左子树要对应右孩子的右子树左孩子的右子树要对应右孩子的左子树整个对应关系是交叉的。我第一次做的时候就是没转过这个弯直接用“两棵树相同”的逻辑去套结果遇到非对称的用例就会报错。所以解题第一步不是急着写代码而是把“对称”翻译成递归或迭代时能用的条件。根节点不用比较因为它只有自己一个点没有镜像对象。真正要比较的是它下面分裂出来的左右两侧子树把它们看成两棵树判断这两棵树是不是互为镜像。1.2 为什么这道题值得刷三遍这道题在力扣上是“简单”难度但它的价值远不止简单题。首先它是热题100的成员在很多公司的笔试面试中出现频率很高尤其是字节、腾讯这类爱考基础数据结构的团队。其次递归和迭代两种解法正好覆盖了二叉树题目的两大通用技巧递归三要素以及用队列或者栈模拟遍历过程。把这题吃透了后面做“相同的树”“二叉树的镜像”“翻转二叉树”等题目会顺手很多。另外这道题也经常被拿来当面试开场题。面试官不会只让你说一个解而是会问“你还会别的写法吗”“两者的空间复杂度分别是什么”。如果你只会递归或者只会迭代答得就不够饱满。所以我的建议是递归、迭代、层序三种思路都自己写一遍写完之后再复盘收获会大得多。2. 递归解法最简单的对称判断2.1 递归的拆解思路递归解法的核心是定义一个函数用来比较两个节点是否互为镜像。这个函数不能只接收 root因为根节点没有镜像点真正需要比较的是 root.left 和 root.right 这两棵子树。所以我们要额外写一个辅助函数入参是两个节点 left 和 right返回一个布尔值表示以 left 为根的子树和以 right 为根的子树是否互为镜像。递归的终止条件有三层缺一不可如果 left 和 right 都是空说明两侧都到头了返回 True。如果 left 和 right 中只有一个为空说明结构不对称返回 False。如果 left.val ! right.val说明节点值不匹配返回 False。通过这三层之后说明当前这两个节点本身是匹配的。接下来要递归判断它们的子树是否镜像left.left 和 right.right 是否镜像left.right 和 right.left 是否镜像。只有这两组同时成立整体才算对称。这里有个小技巧递归函数的返回值应该写成isSymmetricHelper(left.left, right.right) and isSymmetricHelper(left.right, right.left)。注意中间用 and而不是 or因为必须两个方向都满足。如果写成 or那只要有一个方向对称就返回 True整个逻辑就废了。2.2 代码实现与复杂度分析用 Python 写最简洁的版本class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True return self.is_mirror(root.left, root.right) def is_mirror(self, left: TreeNode, right: TreeNode) - bool: if not left and not right: return True if not left or not right: return False if left.val ! right.val: return False return self.is_mirror(left.left, right.right) and \ self.is_mirror(left.right, right.left)这段代码有几点值得学习。第一入口函数负责处理空树或单节点的情况if not root直接返回 True避免后面访问 root.left 报空指针。第二辅助函数独立职责清晰。第三递归调用时用反斜杠换行让对应关系一目了然。时间复杂度是 O(n)因为每个节点最多被访问一次这里的 n 是二叉树节点总数。空间复杂度是 O(n)这里的 n 理解成递归深度更准确最坏情况下树退化成一条链递归深度达到 n栈空间就是 O(n)。如果是一棵完全二叉树递归深度是 log n空间复杂度可以认为是 O(log n)但力扣官方给的最坏情况空间复杂度仍然是 O(n)。2.3 递归解法的易错点第一个易错点是只判断左子树和右子树的值忽略了结构。比如左子树有两个孩子右子树只有一个孩子即便某个方向值碰巧一样整体也不可能对称。所以递归终止条件里的“一个为空另一个非空”必须单独写不能靠后面的值比较来兜底。第二个易错点是递归调用传错参数。很多人会把is_mirror(left.left, left.right)写出来这样等于拿同一个节点的左右孩子去比较完全跑偏了。写递归的时候心里要明确当前比较的 left 和 right 是两个镜像节点它们的孩子要继续按照交叉方式配对。第三个易错点是忘记考虑 root 为 None 的情况。力扣的层序遍历序列可以包含空值但 root 本身可能是 None这时候整棵树没有节点按照定义是对称的所以要返回 True。很多解法省略了这个判断直接访问 root.left 就会抛 AttributeError。3. 迭代解法用队列/栈模拟层序比较3.1 迭代思路把镜像节点成对压入递归虽然简洁但面试官经常追问“能不能不用递归”。答“能”之后就需要用迭代。迭代的核心思想是手动维护一个队列或者栈代替递归时的系统调用栈。思路是这样的初始时把 root.left 和 root.right 这一对节点压入队列。然后每次从队列中弹出两个节点进行比较。比较逻辑和递归完全一样两个都空继续一个空一个非空返回 False值不相等返回 False。然后按照镜像对应的顺序把left.left和right.right压入队列再把left.right和right.left压入队列。注意要确保它们成对弹出所以每次压入两组每组两个。这里有一个特别重要的细节空节点也要压入队列。不能因为节点为 None 就不压否则队列里弹出的顺序会错乱导致结构不对称的树也被判断成对称。很多初次写迭代解法的人在这里翻车只把非空节点压进去结果丢失了空位信息误判了结构。3.2 代码实现队列版本from collections import deque class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True queue deque() queue.append(root.left) queue.append(root.right) while queue: left queue.popleft() right queue.popleft() if not left and not right: continue if not left or not right: return 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因为每次弹出两个压入四个循环中每次 popleft 两次逻辑上是成对的。使用 deque 而不是 list是因为 deque 的 popleft 是 O(1) 复杂度如果直接用 Python list 的 pop(0) 是 O(n) 复杂度会拖慢整体性能面试时提一句这个细节会显得很专业。这个解法的时间复杂度同样是 O(n)空间复杂度是 O(n)。队列中最多同时存在两层的节点数量级最坏情况下是 O(n)。3.3 迭代 vs 递归考察角度与性能对比很多人在面试时会被问“递归和迭代哪个好”。我的回答是它们没有绝对的好坏递归代码更少、可读性更强迭代避免了递归深度过深导致的栈溢出风险更安全。看表格更清楚维度递归解法迭代解法队列代码量约10行约15行逻辑直观性高直接对应数学定义中需要手动压入出队空间复杂度O(n)最坏递归深度O(n)队列节点数栈溢出风险树高过深时有风险无面试考察点递归三要素、分治思想队列/栈模拟、成对比较意识实际刷题时我建议两种都要掌握。如果面试官让你优化通常希望你能从递归改成迭代因为系统栈深度是有限的极端情况下递归可能爆栈。不过在实际面试中只要你先写出递归再主动补充迭代解法就已经超出大部分候选人的预期了。除了队列也可以使用栈。用栈的思路和队列基本一样只是把先进先出改成后进先出代码上的区别在于用list.append和list.pop()并且初始压栈时也压入 root.left 和 root.right。因为比较节点是成对取出栈的顺序不会影响正确性只要保证每次取出的两个节点是应该比较的那对即可。我给一个栈版本供参考class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True stack [root.left, root.right] while stack: right stack.pop() left stack.pop() if not left and not right: continue if not left or not right: return False if left.val ! right.val: return False stack.append(left.left) stack.append(right.right) stack.append(left.right) stack.append(right.left) return True注意这个版本的弹出顺序先弹出的是最后压入的 right 和 left但是它们原本就是成对的所以没问题。压栈时也要按照成对的顺序压入否则会比较错。4. 实战中常见的坑与排查技巧4.1 边界条件与空指针处理我在实际刷题和帮别人 review 代码时发现最常见的错误集中在边界条件上。这里整理几个高频考察点空树 root None返回 True。只有一个节点返回 True因为只有一个点必然对称。根节点只有一个孩子比如 root.left 有值root.right 为空返回 False。值重复但结构不对的情况比如左子树是 [2, 3, None]右子树是 [2, None, 3]虽然值都是 2/3但结构不对称必须返回 False。递归和迭代的边界处理其实是一样的先判空再判一个空再判值。这个顺序不能乱。如果把“值不相等”放在“一个空一个非空”之前遇到空节点访问 val 就会报错。4.2 如何快速定位错误输出如果你写出来的代码在某个用例上报错除了反复看代码更高效的方式是打印调试。我给一个方法在递归函数开头加一个打印把 left 和 right 的值打出来注意判空这样能看到递归实际比较的节点顺序。比如def is_mirror(self, left, right): if left and right: print(f比较 {left.val} 和 {right.val}) else: print(f比较 {left} 和 {right})通过打印结果你可以直观地看到节点配对是否交叉对应。如果打印出来是 left.left 和 left.right 在比较那就是递归参数写错了。如果打印结果显示一侧已经为空另一侧还有节点那就是结构不对称程序早退也能帮你确认逻辑走到哪个分支。迭代解法的调试思路是给队列里的每个节点做一个标记比如用(节点, 位置)的形式但这样会占用额外空间。我更推荐用一个简单办法先写一个层序遍历辅助函数把每一层的节点按顺序打印出来然后用视觉反馈发现对称破缺的地方。不过实际刷题时很少用这么重的调试方式通常只要理清“成对比较”的思路问题就能定位到相应代码段。4.3 变形题与延伸思路对称二叉树不是孤立的知识点它和很多题目是亲戚。比如力扣100“相同的树”递归函数是isSameTree(p, q)入参也是两个节点但比较的是 p.left 和 q.left、p.right 和 q.right方向是顺着的。而我们的对称二叉树需要比较left.left 和 right.right、left.right 和 right.left方向是交叉的。这两个题对比着看能更清楚地区分“单向对应”和“镜像对应”。还有力扣226“翻转二叉树”翻转后的结果如果和原树相同那原树就是对称的。不过这并不适合直接作为解题思路因为翻转再比较需要复制一棵树复杂度更高。但面试时你可以把这个关联关系说出来展示你对题目之间的联系有思考。力扣572“另一棵树的子树”也用到了递归比较两棵树的逻辑虽然判断的是子树关系但基础比较函数和“相同的树”几乎一样。所以吃透对称二叉树其实是为后续一堆二叉树递归题打底子。5. 刷题心得与扩展建议5.1 我刷这道题的真实过程我最初是在一个面试模拟题单里遇到它的当时只写出了递归还要面试官提示才恶补了迭代。后来我把这道题反复做了三遍每次隔两个星期重做一次直到拿到题目不需要思考就能准确写出递归。到第三遍时我开始琢磨队列版本里的空节点到底该不该压入然后自己去验证了一个用例左子树是 [2, None, 3]右子树是 [2, 3, None]。这棵树节点都是 2、3但结构不对称因为左子树的右孩子是 3右子树却只有左孩子是 3。如果队列里不压入空节点两个 3 可能会被误认为是对称的但压入空节点后left.right3和right.rightNone一对会立刻返回 False。所以迭代版本中压入空节点的这个操作是保证结构判断正确的关键这一点我在面试时也不止一次拿出来讲过。5.2 面试时怎么答出亮点如果面试官让你做这题我的建议是先用 30 秒理清思路然后完整地说一遍“递归法”的思路包括入参为什么是两个节点、终止条件为什么有三层、递归调用为什么要交叉对应。写代码时要注意代码风格变量名起得语义清晰比如is_mirror比f好得多。写完递归后可以主动说“我还能写一个迭代版本用队列层次遍历的方式实现避免了递归深度问题”。然后迅速写一遍。写完后如果还有时间可以补充一句“两种解法的复杂度都是 O(n) 时间、O(n) 空间但迭代的栈空间是堆内存分配的递归是系统栈实际操作上迭代更稳健”。这会让面试官觉得你不是背题而是真的理解底层差异。如果面试官进一步问“能不能做到 O(1) 空间”那正常情况下比较难因为二叉树本身结构决定至少需要遍历所有节点。你可以坦诚地说“在不修改树结构的前提下无法做到严格 O(1) 空间但可以尝试 Morris 遍历相关做法不过这里不适合”。一般来说问到这个深度已经很少。5.3 下一步练习建议刷完对称二叉树建议按这个顺序加深100 相同的树 - 101 对称二叉树 - 226 翻转二叉树 - 102 二叉树的层序遍历 - 104 二叉树的最大深度。这几道题把递归、遍历、队列都用到了而且互相之间有很强的关联性。如果你在准备热题 100那么对称二叉树是必刷的第 101 题但后面还有二叉树的中序遍历、从前序与中序遍历序列构造二叉树、二叉树展开为链表等题目它们需要的预处理和递归思路更高阶。把 101 题的基础打牢再做那些题的时候至少不会因为“两棵树比较”这类基础操作卡壳。说到底对称二叉树考的本质就是你能不能把一个看起来是“整体”的题目拆成一对节点、两两比较的子问题。能拆解出来递归和迭代都顺手拆不出来背再多题解也会忘。我在实际刷题时最大的感受是这一类基础题一定不要只写一遍就过隔几天重新写一遍用迭代解法写一次会发现自己对二叉树结构的理解又深了一层。最后再分享一个小习惯每次提交通过后去力扣题解区翻一翻其他语言的写法尤其是官方解法。哪怕你不熟悉那个语言也能看到不同人对同一逻辑的表述方式。对称二叉树这道题有个用 C 的解法用了 lambda 表达式写递归很惊艳我当时看完觉得递归还能这么封装挺有意思的。刷题最大意义不在于背答案而是在一次次对比中找到属于自己的那套解题语言。