不用引入太多背景直接说结论力扣第101题“对称二叉树”是一道非常典型的二叉树递归/迭代练习题也是面试里出现频率很高的基础题。很多人在刚接触二叉树时被遍历、深度、翻转这些概念绕晕等做到“对称”这道题时又开始混淆“左右子树相等”和“镜像对称”的区别。这篇文章我直接把这道题从头拆到尾从题目本质、递归解法的思考方式、迭代解法的队列写法到容易踩的坑和可以延伸的知识点一次性讲透。先明确我要解决的问题给定一棵二叉树的根节点root检查它是否轴对称。所谓轴对称就是这棵树从中间画一条竖线左右两侧是镜像关系。注意不是左子树和右子树完全相同而是左子树的左孩子要对应右子树的右孩子左子树的右孩子要对应右子树的左孩子。这个对应关系是整道题的灵魂。1. 题目拆解对称的本质是“镜像比较”1.1 从一棵树到两棵树的转化第一次看到这道题很多人的第一反应是我能不能把左子树翻转一下然后和右子树比较这是一个很自然的思路但实际操作起来会多出额外步骤比如要先写一个翻转树的函数然后再写一个判断两棵树是否相同的函数两个函数叠在一起逻辑上绕了一圈。更直接的思路是既然对称是镜像关系那我不需要真的翻转而是同时遍历左子树和右子树每次比较两个对应位置的节点。也就是说把“判断一棵树是否对称”拆成“判断两棵树是否镜像对称”。这个转化非常关键。它把一个看似只涉及单棵树的问题变成了双树比较问题。很多二叉树的题目都是这个套路比如判断两棵树是否相同也是同时遍历两棵树。对称只是在这个基础上把左右孩子的访问顺序换了一下。1.2 镜像比较的三个条件对于两棵子树p和q它俩互为镜像必须同时满足三个条件p.val q.val也就是当前节点的值相等。p.left和q.right互为镜像即 p 的左孩子要对应 q 的右孩子。p.right和q.left互为镜像即 p 的右孩子要对应 q 的左孩子。为什么是交叉对应因为镜像嘛。你对着镜子举左手镜子里的人举的是右手。所以左对右右对左这就是镜像的核心。有了这三个条件写递归就水到渠成了。递归函数接收两个节点先判断值再递归判断它们的孩子。终止条件是两个节点都为空返回 true一个为空一个不为空返回 false。1.3 力扣原题给出的小陷阱原题给的例子很简单1 / \ 2 2 / \ / \ 3 4 4 3这个是对称的。但很多人看例子会误以为“只要左右孩子值相等就行”于是写出了只比较root.left.val root.right.val就返回 true 的代码。这在大数据量下一定错。还有一种常见误解是把对称理解为“左子树的先序遍历结果等于右子树的后序遍历结果”。这个思路在特定条件下能工作但需要考虑空节点的表示而且实现起来不如直接递归直观。我建议初学者先掌握递归和迭代两种标准解法再考虑这些花式技巧。2. 递归解法短路思想与边界条件的处理2.1 核心代码与逐行解释递归解法是这道题最简洁的写法。我用 Python 写了一遍结构非常清晰class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True def check(p: Optional[TreeNode], q: Optional[TreeNode]) - bool: if not p and not q: return True if not p or not q: return False if p.val ! q.val: return False return check(p.left, q.right) and check(p.right, q.left) return check(root.left, root.right)这段代码里有几个细节值得展开讲第一个细节是if not root: return True。空树算不算对称在力扣的定义里空树是对称的。这符合数学上“空集满足任意性质”的约定在递归时也天然成立因为根节点为空时左右子树都不存在。第二个细节是把递归函数定义在isSymmetric内部。这样可以方便地访问根节点的左右孩子也避免了额外传参。当然你也可以定义成外部函数传入root.left和root.right效果一样。第三个细节是递归的终止条件顺序。先判断两个都空再判断一个空最后才比较值。这个顺序不能乱。如果先比较值空节点会直接报错。在 Python 里对None取.val会抛AttributeError所以在任何递归里空节点判断都要放在最前面。第四个细节是check(p.left, q.right) and check(p.right, q.left)这个表达式。Python 的and是短路求值的也就是说如果左边返回 False右边根本不会执行。这在递归里天然形成剪枝一旦发现不对称立刻终止递归不会白白遍历整棵树。2.2 递归过程的手动模拟为了彻底理解递归的执行过程我拿上面那个对称的例子手动走一遍。根节点是 1进入check(root.left, root.right)也就是check(节点2, 节点2)。第一步两个节点都不为空值都是 2相等。第二步递归调用check(节点2.left, 节点2.right)也就是check(节点3, 节点4)。两个节点值分别为 3 和 4不相等返回 False。等等这个例子里节点3和4都是叶子节点正常情况下左边是3右边是4不对称吗注意我这里用的是力扣例子里的结构1 / \ 2 2 / \ / \ 3 4 4 3根节点 1 的左孩子的左孩子是 3根节点 1 的右孩子的右孩子是 3。所以在check(root.left, root.right)里p.left是左侧的 3q.right是右侧的 3两个值相等。而p.right是左侧的 4q.left是右侧的 4两个值也相等。只有当树变成1 / \ 2 2 / \ / \ 3 4 3 4这种情况下左侧的 3 对应右侧的左孩子 3但镜像对应的是右侧的右孩子 4才会立刻发现不对称。我在实际模拟时经常把指向搞混后来总结了一个口诀递归时只关心“当前这一层传入的两个节点”剩下的交给下一层。只要记住了左对右、右对左递归的调用关系就不会错。2.3 递归的时间与空间复杂度分析时间复杂度是 O(n)n 是二叉树的节点数。因为每个节点最多被访问一次最坏情况下对称时递归会遍历整棵树的所有节点。如果不对称可能会提前终止但最坏复杂度仍然是 O(n)。空间复杂度是 O(n) 的额外空间因为递归调用栈的深度取决于树的高度。最坏情况是树退化成链表高度为 n递归栈会压入 n 层。最好的情况是平衡树高度为 log(n)空间复杂度就是 O(log n)。面试时如果被问到空间复杂度要把这两种情况都说清楚只答 O(n) 或 O(log n) 都不完整考官想听的是你理解树高度对递归栈的影响。3. 迭代解法队列实现层序式成对校验3.1 为什么递归不够还要学迭代递归解法虽然简洁但也有天然短板。当树的深度很大时递归调用栈可能会溢出这是函数调用机制决定的。比如树退化成一条链深度达到几万层Python 默认的递归深度限制是 1000 左右直接 RecursionError。迭代解法则没有这个顾虑它用显式的队列或栈来模拟递归过程不依赖系统调用栈。这也是面试官喜欢追问的第二问“能不能不用递归实现”如果只会递归写法面试印象分会打折扣。3.2 队列模拟的核心思路迭代解法的思路是把需要比较的两个节点成对放入队列每次从队首取出两个节点进行比较然后把它们的镜像子节点成对入队。具体步骤如下初始化队列将root.left和root.right成对入队。从队列中取出两个节点u和v。如果u和v都为空跳过本轮循环。如果u或v只有一个为空返回 False。如果u.val ! v.val返回 False。将u.left与v.right成对入队再将u.right与v.left成对入队。循环直到队列为空返回 True。注意入队的顺序必须是两两一组不能只入队一个节点。我用 Python 实现时习惯用collections.deque因为列表的pop(0)是 O(n) 的而deque的popleft()是 O(1) 的。from collections import deque class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True queue deque([root.left, root.right]) while queue: u queue.popleft() v queue.popleft() if not u and not v: continue if not u or not v: return False if u.val ! v.val: return False queue.append(u.left) queue.append(v.right) queue.append(u.right) queue.append(v.left) return True这段代码里最需要注意的是第六步的入队顺序。u.left必须和v.right配对u.right必须和v.left配对这是镜像的核心。如果写成了u.left和v.left配对那就是在判断两棵树是否相等而不是是否镜像。这个错误非常隐蔽尤其在队列很长时很难一眼看出来我自己就曾经在这种地方排查了很久。3.3 用栈替代队列殊途同归队列解法用到了先进先出的特性但实际上用栈也能实现只要保持成对弹入弹出的顺序不变即可。如果你把上面的queue换成普通的 list用append和pop()模拟栈效果完全一样。这是因为我们只关心“成对比较”这个约束不关心比较的先后顺序。无论是 BFS 式的层序比较还是 DFS 式的深度优先比较只要每对节点是镜像对应的最终结果都一样。在面试时主动提一句“队列和栈都可以因为比较顺序不影响结果”会显得你对问题的理解更深一层。这也是从“会做题”到“懂原理”的一个小分水岭。3.4 迭代解法的复杂度对比迭代解法的时空复杂度都是 O(n)。时间上每个节点入队出队一次空间上队列最多同时存储两层的节点最坏情况下完全二叉树最后一层有约 n/2 个节点所以空间复杂度也是 O(n)。和递归相比迭代的优势在于没有调用栈溢出的风险。劣势是代码相对啰嗦而且容易在入队顺序上写错。我觉得两者没有绝对的优劣关键是理解各自的适用场景面试时首选递归写起来快实际工程里如果树可能很深用迭代更稳。4. 常见误判与调试技巧实录4.1 误区一直接比较左右子树先序遍历序列想过用序列化来偷懒的朋友应该不少。思路是把左子树做一次先序遍历把右子树做一次后序遍历如果序列相同就对称。这个思路理论上说得通但实现时有个大坑空节点怎么表示。如果不用特殊字符标记空节点光靠节点值序列很多树会得到相同的序列。比如下面的两棵树1 1 / \ / \ 2 2 2 2 / \ 3 3它们的节点值序列都是 1, 2, 3, 2 或 1, 2, 2, 3单靠值序列根本区分不开。所以如果非要用序列化一定要用例如#来代表空节点并且保证左右子树的遍历方向相反。这个问题在讨论“对称树”这类问题时很容易被忽略但实际写代码时一定会踩坑。4.2 误区二只做层序遍历并检查每层回文另一个常见的思路是用层序遍历收集每一层的节点值然后检查每一层是不是回文数组。这个思路能通过一些测试用例但会在一种情况下出问题空节点的位置没有被保留。比如下面的树1 / \ 2 2 \ \ 3 3第一层是 [1]第二层是 [2, 2]第三层如果只收集非空值是 [3, 3]看起来是回文但这棵树实际上不是对称的因为左边 3 是右孩子右边 3 也是右孩子位置不对应。解决办法是层序遍历时保留空节点的占位符比如用None表示空然后再检查回文。这样可行但实现起来比迭代解法更繁琐而且队列里可能塞入大量空节点空间利用率不高。我觉得作为思路拓展可以聊一聊但不建议作为面试时的首选解法。4.3 实际调试中我常用的三个小技巧技巧一是多用“不对称”的例子来验证。比如只修改树中一个节点的值确保代码能检测出来。很多人测试时只拿对称的例子跑一遍通过就以为没问题结果换了个用例就挂。我习惯准备至少三个用例对称树、非对称树、空树。技巧二是打印递归的调用对。在递归函数入口加一行print(p.val if p else None, q.val if q else None)可以看到每层比较的是哪两个节点。这一步对排查镜像对应关系极有帮助。技巧三是在迭代解法中不要把成对的节点塞进队列后忘了校验队列长度。因为每次循环取出两个节点如果入队时不小心只塞了一个队列长度变成奇数就会在下一次popleft()时抛异常。比较好的习惯是每次入队都成对append循环体内先判断len(queue) 2再做操作。5. 从对称二叉树延伸二叉树的深度、遍历与搜索树的交叉联想5.1 对称与遍历不改变不破坏原有结构学完对称二叉树再回头看热搜词里的“二叉树的遍历”你会发现它们其实是同一套思维体系。遍历的核心是“访问顺序”对称的核心是“比较顺序”。如果你能把二叉树的先序、中序、后序、层序遍历都写熟练对称题里的递归和队列写法就只是换了个用途而已。比如迭代解法中我用队列成对取节点本质就是层序遍历的变形。层序遍历每次取一个节点并访问它的左右孩子对称迭代每次取两个节点并比较它们的镜像子节点。如果你对层序遍历的模板足够熟悉这个变形不需要死记硬背现场推就能推出来。“二叉树的深度”这个热搜词也和对称有关联。对称树不一定平衡但平衡树大概率看起来更对称。深度本身不直接参与对称判断但递归解法的空间复杂度来自深度所以理解深度对分析递归栈有帮助。5.2 对称与搜索二叉树验证顺序的另一个方向搜索二叉树BST定义的是节点值的排序关系左孩子小于根右孩子大于根。对称二叉树定义的是结构关系两者不冲突但也不等价。一棵 BST 完全可能不对称比如5 / \ 3 8 / \ 1 4按 BST 规则是合法的但左右子树并不镜像对称。如果把这两类问题放在一起复习你会发现二叉树的题目基本都是三板斧递归函数的设计、遍历顺序的选择、边界条件的处理。对称二叉树同时用到了递归和层序迭代是一道很好的综合训练题。5.3 变体题怎么判断一棵树的子树是否对称面试官经常会在原题基础上加问一句“如果给你一个根节点如何找到这棵树中最大的对称子树”这个问题的思路是遍历每个节点以该节点为根判断是否对称同时记录最大深度。判断函数可以直接复用原题的isSymmetric整体时间复杂度是 O(n^2)。如果追求更优解可以用后序遍历加上子树哈希的手段来降低重复计算但这是比较进阶的玩法初学者先掌握 O(n^2) 的暴力解法即可。这类变体题的价值在于它逼着你把一个函数抽象成可复用的工具函数。原题里check(p, q)比较的是两个节点放到变体里就变成了一个独立的判断逻辑被反复调用。很多人拿到变体题就懵本质上是没有意识到“原题已经被我写成了一个完整的函数”。6. 实际面试中怎么回答这道题才能加分6.1 从“背题”到“讲题”力扣上有不少人是靠背答案过题的但面试官早就免疫了。你光背出递归代码他马上追问迭代写法你写出迭代他又问复杂度你答出复杂度他还能问“如果树非常大递归栈会怎样”。这也是我反复强调要理解原理的原因。我建议的回答顺序是先说对称的定义左对右、右对左再说递归解法三个终止条件加一个递归式接着补充迭代解法队列成对比较最后主动分析复杂度。每一步都用一句人话解释“为什么”面试官会明显感受到你是真懂。6.2 一道题背后的知识网络这道题虽然简单但牵扯出来的知识点其实覆盖了二叉树的大部分基础递归思想的落地、队列的运用、树的深度、空节点的处理、复杂度分析。如果你刚刚开始刷二叉树把这道题吃透再去做“相同的树”“翻转二叉树”“二叉树的最大深度”会顺畅许多因为它们共用同一套思维模型。就我自己的刷题体验来说最容易提升效率的方法不是刷题数量而是每做完一道题花十分钟想一想这道题和之前哪道题相似代码的骨架能不能抽出来换一个条件会变成什么题“对称二叉树”就是一个特别适合做这种思考的样本因为它简单到不吓人又复杂到足够承载递归、迭代、边界处理和复杂度分析四块内容。7. 最后的实操建议与个人体会我刷这道题的时候最深的体会是递归代码写得快不代表理解到位。评判标准是你能不能在没有提示的前提下把递归改成迭代。改完之后再试试用层序遍历回文检测法做一遍虽然不推荐面试使用但能帮你深刻理解空节点占位的重要性。做这道题时还建议准备几个容易出错的用例包括只有根节点、节点值都为负数、左右子树高度差很大等情况。把这些用例跑通基本上代码的鲁棒性就过关了。我个人习惯在做完题后额外写一个“临时修改某个节点值”的小函数用来快速生成不对称的测试数据这样就不用每次手动构造一棵新树了。最后再分享一个调试小细节如果你用的是 Python递归函数里要避免直接使用全局变量来传参尽量把需要比较的数据都放在函数参数里否则在多层递归时容易出现状态污染。队列迭代也一样不要在一个 while 循环里改动其他无关变量保持每个循环周期独立。把这类工程习惯带到刷题里时间长了你会发现自己的代码质量和调 bug 速度都会上一个台阶。
力扣101：对称二叉树的递归与迭代解法详解
不用引入太多背景直接说结论力扣第101题“对称二叉树”是一道非常典型的二叉树递归/迭代练习题也是面试里出现频率很高的基础题。很多人在刚接触二叉树时被遍历、深度、翻转这些概念绕晕等做到“对称”这道题时又开始混淆“左右子树相等”和“镜像对称”的区别。这篇文章我直接把这道题从头拆到尾从题目本质、递归解法的思考方式、迭代解法的队列写法到容易踩的坑和可以延伸的知识点一次性讲透。先明确我要解决的问题给定一棵二叉树的根节点root检查它是否轴对称。所谓轴对称就是这棵树从中间画一条竖线左右两侧是镜像关系。注意不是左子树和右子树完全相同而是左子树的左孩子要对应右子树的右孩子左子树的右孩子要对应右子树的左孩子。这个对应关系是整道题的灵魂。1. 题目拆解对称的本质是“镜像比较”1.1 从一棵树到两棵树的转化第一次看到这道题很多人的第一反应是我能不能把左子树翻转一下然后和右子树比较这是一个很自然的思路但实际操作起来会多出额外步骤比如要先写一个翻转树的函数然后再写一个判断两棵树是否相同的函数两个函数叠在一起逻辑上绕了一圈。更直接的思路是既然对称是镜像关系那我不需要真的翻转而是同时遍历左子树和右子树每次比较两个对应位置的节点。也就是说把“判断一棵树是否对称”拆成“判断两棵树是否镜像对称”。这个转化非常关键。它把一个看似只涉及单棵树的问题变成了双树比较问题。很多二叉树的题目都是这个套路比如判断两棵树是否相同也是同时遍历两棵树。对称只是在这个基础上把左右孩子的访问顺序换了一下。1.2 镜像比较的三个条件对于两棵子树p和q它俩互为镜像必须同时满足三个条件p.val q.val也就是当前节点的值相等。p.left和q.right互为镜像即 p 的左孩子要对应 q 的右孩子。p.right和q.left互为镜像即 p 的右孩子要对应 q 的左孩子。为什么是交叉对应因为镜像嘛。你对着镜子举左手镜子里的人举的是右手。所以左对右右对左这就是镜像的核心。有了这三个条件写递归就水到渠成了。递归函数接收两个节点先判断值再递归判断它们的孩子。终止条件是两个节点都为空返回 true一个为空一个不为空返回 false。1.3 力扣原题给出的小陷阱原题给的例子很简单1 / \ 2 2 / \ / \ 3 4 4 3这个是对称的。但很多人看例子会误以为“只要左右孩子值相等就行”于是写出了只比较root.left.val root.right.val就返回 true 的代码。这在大数据量下一定错。还有一种常见误解是把对称理解为“左子树的先序遍历结果等于右子树的后序遍历结果”。这个思路在特定条件下能工作但需要考虑空节点的表示而且实现起来不如直接递归直观。我建议初学者先掌握递归和迭代两种标准解法再考虑这些花式技巧。2. 递归解法短路思想与边界条件的处理2.1 核心代码与逐行解释递归解法是这道题最简洁的写法。我用 Python 写了一遍结构非常清晰class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True def check(p: Optional[TreeNode], q: Optional[TreeNode]) - bool: if not p and not q: return True if not p or not q: return False if p.val ! q.val: return False return check(p.left, q.right) and check(p.right, q.left) return check(root.left, root.right)这段代码里有几个细节值得展开讲第一个细节是if not root: return True。空树算不算对称在力扣的定义里空树是对称的。这符合数学上“空集满足任意性质”的约定在递归时也天然成立因为根节点为空时左右子树都不存在。第二个细节是把递归函数定义在isSymmetric内部。这样可以方便地访问根节点的左右孩子也避免了额外传参。当然你也可以定义成外部函数传入root.left和root.right效果一样。第三个细节是递归的终止条件顺序。先判断两个都空再判断一个空最后才比较值。这个顺序不能乱。如果先比较值空节点会直接报错。在 Python 里对None取.val会抛AttributeError所以在任何递归里空节点判断都要放在最前面。第四个细节是check(p.left, q.right) and check(p.right, q.left)这个表达式。Python 的and是短路求值的也就是说如果左边返回 False右边根本不会执行。这在递归里天然形成剪枝一旦发现不对称立刻终止递归不会白白遍历整棵树。2.2 递归过程的手动模拟为了彻底理解递归的执行过程我拿上面那个对称的例子手动走一遍。根节点是 1进入check(root.left, root.right)也就是check(节点2, 节点2)。第一步两个节点都不为空值都是 2相等。第二步递归调用check(节点2.left, 节点2.right)也就是check(节点3, 节点4)。两个节点值分别为 3 和 4不相等返回 False。等等这个例子里节点3和4都是叶子节点正常情况下左边是3右边是4不对称吗注意我这里用的是力扣例子里的结构1 / \ 2 2 / \ / \ 3 4 4 3根节点 1 的左孩子的左孩子是 3根节点 1 的右孩子的右孩子是 3。所以在check(root.left, root.right)里p.left是左侧的 3q.right是右侧的 3两个值相等。而p.right是左侧的 4q.left是右侧的 4两个值也相等。只有当树变成1 / \ 2 2 / \ / \ 3 4 3 4这种情况下左侧的 3 对应右侧的左孩子 3但镜像对应的是右侧的右孩子 4才会立刻发现不对称。我在实际模拟时经常把指向搞混后来总结了一个口诀递归时只关心“当前这一层传入的两个节点”剩下的交给下一层。只要记住了左对右、右对左递归的调用关系就不会错。2.3 递归的时间与空间复杂度分析时间复杂度是 O(n)n 是二叉树的节点数。因为每个节点最多被访问一次最坏情况下对称时递归会遍历整棵树的所有节点。如果不对称可能会提前终止但最坏复杂度仍然是 O(n)。空间复杂度是 O(n) 的额外空间因为递归调用栈的深度取决于树的高度。最坏情况是树退化成链表高度为 n递归栈会压入 n 层。最好的情况是平衡树高度为 log(n)空间复杂度就是 O(log n)。面试时如果被问到空间复杂度要把这两种情况都说清楚只答 O(n) 或 O(log n) 都不完整考官想听的是你理解树高度对递归栈的影响。3. 迭代解法队列实现层序式成对校验3.1 为什么递归不够还要学迭代递归解法虽然简洁但也有天然短板。当树的深度很大时递归调用栈可能会溢出这是函数调用机制决定的。比如树退化成一条链深度达到几万层Python 默认的递归深度限制是 1000 左右直接 RecursionError。迭代解法则没有这个顾虑它用显式的队列或栈来模拟递归过程不依赖系统调用栈。这也是面试官喜欢追问的第二问“能不能不用递归实现”如果只会递归写法面试印象分会打折扣。3.2 队列模拟的核心思路迭代解法的思路是把需要比较的两个节点成对放入队列每次从队首取出两个节点进行比较然后把它们的镜像子节点成对入队。具体步骤如下初始化队列将root.left和root.right成对入队。从队列中取出两个节点u和v。如果u和v都为空跳过本轮循环。如果u或v只有一个为空返回 False。如果u.val ! v.val返回 False。将u.left与v.right成对入队再将u.right与v.left成对入队。循环直到队列为空返回 True。注意入队的顺序必须是两两一组不能只入队一个节点。我用 Python 实现时习惯用collections.deque因为列表的pop(0)是 O(n) 的而deque的popleft()是 O(1) 的。from collections import deque class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True queue deque([root.left, root.right]) while queue: u queue.popleft() v queue.popleft() if not u and not v: continue if not u or not v: return False if u.val ! v.val: return False queue.append(u.left) queue.append(v.right) queue.append(u.right) queue.append(v.left) return True这段代码里最需要注意的是第六步的入队顺序。u.left必须和v.right配对u.right必须和v.left配对这是镜像的核心。如果写成了u.left和v.left配对那就是在判断两棵树是否相等而不是是否镜像。这个错误非常隐蔽尤其在队列很长时很难一眼看出来我自己就曾经在这种地方排查了很久。3.3 用栈替代队列殊途同归队列解法用到了先进先出的特性但实际上用栈也能实现只要保持成对弹入弹出的顺序不变即可。如果你把上面的queue换成普通的 list用append和pop()模拟栈效果完全一样。这是因为我们只关心“成对比较”这个约束不关心比较的先后顺序。无论是 BFS 式的层序比较还是 DFS 式的深度优先比较只要每对节点是镜像对应的最终结果都一样。在面试时主动提一句“队列和栈都可以因为比较顺序不影响结果”会显得你对问题的理解更深一层。这也是从“会做题”到“懂原理”的一个小分水岭。3.4 迭代解法的复杂度对比迭代解法的时空复杂度都是 O(n)。时间上每个节点入队出队一次空间上队列最多同时存储两层的节点最坏情况下完全二叉树最后一层有约 n/2 个节点所以空间复杂度也是 O(n)。和递归相比迭代的优势在于没有调用栈溢出的风险。劣势是代码相对啰嗦而且容易在入队顺序上写错。我觉得两者没有绝对的优劣关键是理解各自的适用场景面试时首选递归写起来快实际工程里如果树可能很深用迭代更稳。4. 常见误判与调试技巧实录4.1 误区一直接比较左右子树先序遍历序列想过用序列化来偷懒的朋友应该不少。思路是把左子树做一次先序遍历把右子树做一次后序遍历如果序列相同就对称。这个思路理论上说得通但实现时有个大坑空节点怎么表示。如果不用特殊字符标记空节点光靠节点值序列很多树会得到相同的序列。比如下面的两棵树1 1 / \ / \ 2 2 2 2 / \ 3 3它们的节点值序列都是 1, 2, 3, 2 或 1, 2, 2, 3单靠值序列根本区分不开。所以如果非要用序列化一定要用例如#来代表空节点并且保证左右子树的遍历方向相反。这个问题在讨论“对称树”这类问题时很容易被忽略但实际写代码时一定会踩坑。4.2 误区二只做层序遍历并检查每层回文另一个常见的思路是用层序遍历收集每一层的节点值然后检查每一层是不是回文数组。这个思路能通过一些测试用例但会在一种情况下出问题空节点的位置没有被保留。比如下面的树1 / \ 2 2 \ \ 3 3第一层是 [1]第二层是 [2, 2]第三层如果只收集非空值是 [3, 3]看起来是回文但这棵树实际上不是对称的因为左边 3 是右孩子右边 3 也是右孩子位置不对应。解决办法是层序遍历时保留空节点的占位符比如用None表示空然后再检查回文。这样可行但实现起来比迭代解法更繁琐而且队列里可能塞入大量空节点空间利用率不高。我觉得作为思路拓展可以聊一聊但不建议作为面试时的首选解法。4.3 实际调试中我常用的三个小技巧技巧一是多用“不对称”的例子来验证。比如只修改树中一个节点的值确保代码能检测出来。很多人测试时只拿对称的例子跑一遍通过就以为没问题结果换了个用例就挂。我习惯准备至少三个用例对称树、非对称树、空树。技巧二是打印递归的调用对。在递归函数入口加一行print(p.val if p else None, q.val if q else None)可以看到每层比较的是哪两个节点。这一步对排查镜像对应关系极有帮助。技巧三是在迭代解法中不要把成对的节点塞进队列后忘了校验队列长度。因为每次循环取出两个节点如果入队时不小心只塞了一个队列长度变成奇数就会在下一次popleft()时抛异常。比较好的习惯是每次入队都成对append循环体内先判断len(queue) 2再做操作。5. 从对称二叉树延伸二叉树的深度、遍历与搜索树的交叉联想5.1 对称与遍历不改变不破坏原有结构学完对称二叉树再回头看热搜词里的“二叉树的遍历”你会发现它们其实是同一套思维体系。遍历的核心是“访问顺序”对称的核心是“比较顺序”。如果你能把二叉树的先序、中序、后序、层序遍历都写熟练对称题里的递归和队列写法就只是换了个用途而已。比如迭代解法中我用队列成对取节点本质就是层序遍历的变形。层序遍历每次取一个节点并访问它的左右孩子对称迭代每次取两个节点并比较它们的镜像子节点。如果你对层序遍历的模板足够熟悉这个变形不需要死记硬背现场推就能推出来。“二叉树的深度”这个热搜词也和对称有关联。对称树不一定平衡但平衡树大概率看起来更对称。深度本身不直接参与对称判断但递归解法的空间复杂度来自深度所以理解深度对分析递归栈有帮助。5.2 对称与搜索二叉树验证顺序的另一个方向搜索二叉树BST定义的是节点值的排序关系左孩子小于根右孩子大于根。对称二叉树定义的是结构关系两者不冲突但也不等价。一棵 BST 完全可能不对称比如5 / \ 3 8 / \ 1 4按 BST 规则是合法的但左右子树并不镜像对称。如果把这两类问题放在一起复习你会发现二叉树的题目基本都是三板斧递归函数的设计、遍历顺序的选择、边界条件的处理。对称二叉树同时用到了递归和层序迭代是一道很好的综合训练题。5.3 变体题怎么判断一棵树的子树是否对称面试官经常会在原题基础上加问一句“如果给你一个根节点如何找到这棵树中最大的对称子树”这个问题的思路是遍历每个节点以该节点为根判断是否对称同时记录最大深度。判断函数可以直接复用原题的isSymmetric整体时间复杂度是 O(n^2)。如果追求更优解可以用后序遍历加上子树哈希的手段来降低重复计算但这是比较进阶的玩法初学者先掌握 O(n^2) 的暴力解法即可。这类变体题的价值在于它逼着你把一个函数抽象成可复用的工具函数。原题里check(p, q)比较的是两个节点放到变体里就变成了一个独立的判断逻辑被反复调用。很多人拿到变体题就懵本质上是没有意识到“原题已经被我写成了一个完整的函数”。6. 实际面试中怎么回答这道题才能加分6.1 从“背题”到“讲题”力扣上有不少人是靠背答案过题的但面试官早就免疫了。你光背出递归代码他马上追问迭代写法你写出迭代他又问复杂度你答出复杂度他还能问“如果树非常大递归栈会怎样”。这也是我反复强调要理解原理的原因。我建议的回答顺序是先说对称的定义左对右、右对左再说递归解法三个终止条件加一个递归式接着补充迭代解法队列成对比较最后主动分析复杂度。每一步都用一句人话解释“为什么”面试官会明显感受到你是真懂。6.2 一道题背后的知识网络这道题虽然简单但牵扯出来的知识点其实覆盖了二叉树的大部分基础递归思想的落地、队列的运用、树的深度、空节点的处理、复杂度分析。如果你刚刚开始刷二叉树把这道题吃透再去做“相同的树”“翻转二叉树”“二叉树的最大深度”会顺畅许多因为它们共用同一套思维模型。就我自己的刷题体验来说最容易提升效率的方法不是刷题数量而是每做完一道题花十分钟想一想这道题和之前哪道题相似代码的骨架能不能抽出来换一个条件会变成什么题“对称二叉树”就是一个特别适合做这种思考的样本因为它简单到不吓人又复杂到足够承载递归、迭代、边界处理和复杂度分析四块内容。7. 最后的实操建议与个人体会我刷这道题的时候最深的体会是递归代码写得快不代表理解到位。评判标准是你能不能在没有提示的前提下把递归改成迭代。改完之后再试试用层序遍历回文检测法做一遍虽然不推荐面试使用但能帮你深刻理解空节点占位的重要性。做这道题时还建议准备几个容易出错的用例包括只有根节点、节点值都为负数、左右子树高度差很大等情况。把这些用例跑通基本上代码的鲁棒性就过关了。我个人习惯在做完题后额外写一个“临时修改某个节点值”的小函数用来快速生成不对称的测试数据这样就不用每次手动构造一棵新树了。最后再分享一个调试小细节如果你用的是 Python递归函数里要避免直接使用全局变量来传参尽量把需要比较的数据都放在函数参数里否则在多层递归时容易出现状态污染。队列迭代也一样不要在一个 while 循环里改动其他无关变量保持每个循环周期独立。把这类工程习惯带到刷题里时间长了你会发现自己的代码质量和调 bug 速度都会上一个台阶。
