刷 LeetCode 的人大概率会在二叉树专题里撞上这道题——判断对称二叉树题号 101英文名 Symmetric Tree。它不是那种一眼就让人发怵的难题但特别有代表性一道题同时考了递归设计、树的结构认知和边界条件处理。我第一次做的时候以为只要分别判断左右子树对称就行结果提交之后被用例教育了。今天这篇文章就把这道题拆开揉碎从题目到底在问什么到递归和迭代两种通解再到我实际踩过的几个坑一次讲清楚。无论你是正在准备算法面试的开发者还是刚系统学二叉树数据结构的初学者看完之后应该都能把对称这两个字真正翻译成代码。你可能已经在各种刷题清单里见过它也知道答案大概长什么样但很多时候只是背会了并没有真正理解为什么这么写。这也是我写这篇的原因与其对着答案默写不如把背后的镜像关系、递归终止条件、队列配对方式都弄明白。后面我还会提到空树、单节点、链式树这些边界场景很多面试官就喜欢在这些小地方挖坑。1. 先搞懂题目到底在问什么1.1 定义什么叫作对称直观来说对称二叉树就是一棵树以根节点所在的中轴线为轴左右两边是镜像的。比如下面这棵树1 / \ 2 2 / \ / \ 3 4 4 3左子树和右子树从根节点 1 往下看是互相照镜子的关系左子树的左侧 3对应右子树的右侧 3左子树的右侧 4对应右子树的左侧 4。你把它想象成一个人站在镜子前左手对应镜中的右手右手对应镜中的左手。判断对称本质上就是在验证左子树和右子树互为镜像。很多人第一次会把对称和相等混在一起。相等是左边一棵树和右边一棵树完全一样对称则要求交叉位置一样。给你一个反例稍微改一下就能看出差别1 / \ 2 2 / \ / \ 3 4 3 4这棵树的左右子树其实是完全相同的但它并不对称因为左下角的 3 应该对应右下角的 4现在却对应到了 3。这就是交叉比较和相同位置比较的本质区别。1.2 对称、相同、翻转三者关系刷到这道题的时候很多教程会顺便提到另外两题LeetCode 100 相同的树以及 LeetCode 226 翻转二叉树。这三题放在一起对比着看会非常清楚。题目核心问题比较方式100. 相同的树两棵树是否完全一样p.left 与 q.left 比p.right 与 q.right 比226. 翻转二叉树把一棵树所有左右子树交换不比较只负责修改结构101. 对称二叉树一棵树自己是否镜像对称左子树的左孩子与右子树的右孩子比左子树的右孩子与右子树的左孩子比这里有一个全文最核心的公式。判断一棵树是否对称等价于判断 root.left 和 root.right 是否互为镜像可以写成isMirror(p, q) (p.val q.val) isMirror(p.left, q.right) isMirror(p.right, q.left)看到这个公式你大概就能明白为什么这道题和相同的树几乎共享同一套递归模板只是比较方向从直比变成了交叉比。另外还有一种等价思路先把树翻转再和原树比较是否相同。这种思路在理解上很有帮助但要注意别直接修改原树要么复制一份要么在递归参数里做虚拟翻转。面试时能主动提到这个等价关系往往是加分项。1.3 边界约定空树对称吗LeetCode 的判定是空树返回 true。很多人第一次写会在 isSymmetric 入口直接按if not root: return True处理也有人觉得空树没有对称性应该返回 false。但刷题平台的标准答案就是空树对称逻辑上也说得通空树没有左右子树自然不存在不对称的节点对。面试时最好主动问一句空树怎么算一般都会按 true 处理你确认一下反而显得严谨。至于单节点树root.left 和 root.right 都是 None辅助函数isMirror(None, None)会返回 true所以单节点天然对称。这两个边界在递归终止条件里其实已经天然涵盖了不需要在入口额外处理单节点的情况。2. 把镜像翻译成递归逻辑2.1 核心转换比较的对象是两棵子树写这道题最容易卡住的地方是不知道该拿谁和谁比。很多人第一反应是判断一个节点的左右孩子是否相等马上发现自己根本写不下去。原因在于对称是一个全局性质只盯着一个节点看是看不出来的。递归的精髓就是把一棵树的问题转化为两个子树的问题。既然是对称那比较对象就天然是两个节点。1 / \ L R在 L 和 R 的下一层镜像对应关系是L.left 对应 R.rightL.right 对应 R.left。为什么是交叉的你想象镜子立在 L 和 R 之间。L 的左外侧是整棵树的左外侧它在镜子里应该对应到 R 的右外侧也就是 R.right。同理L 的右内侧对应 R 的左内侧。所以才有isMirror(p.left, q.right)这种看起来有点拗口的写法它不是笔误而是镜像关系的直接翻译。2.2 递归函数的三个终止条件递归函数isMirror(p, q)的逻辑可以分为四步前三个是终止条件最后是递归推进如果 p 和 q 都是空返回 true。两棵空子树当然是镜像的。如果 p 和 q 中只有一个为空返回 false。一棵有节点、一棵没有节点结构已经不一样了。如果 p.val 和 q.val 不相等返回 false。继续递归比较 p.left 与 q.right以及 p.right 与 q.left两个结果都要成立。这里极其重要的是顺序。必须先处理空值再去访问 val。如果一上来就写if p.val ! q.val而 p 恰好是 None程序会直接抛空指针异常。这个顺序问题我在第四节还会展开说因为它是新手最容易踩的坑。有经验的开发者可能会写更紧凑的版本if not p or not q: return p is q用p is q判断两个对象是否同为 None。这种写法没问题但初学者建议还是拆成两行可读性更高也不容易出错。2.3 迭代解法的队列设计递归写完之后面试官经常追问一句如果不让用递归你怎么实现 这时候就需要迭代解法。迭代解法不需要调用栈而是用一个队列显式地维护待比较的节点对。核心思路是每次从队列里取出两个节点比较它们的值然后按镜像位置把它们的下一层节点成对放回去。具体来说初始化队列把 root.left 和 root.right 作为第一对放进去。循环直到队列为空。每次取出两个节点 p 和 q。如果 p 和 q 都是空继续下一轮。如果 p、q 中有一个为空或者值不相等直接返回 false。把 p.left 和 q.right 放进去再把 p.right 和 q.left 放进去。这里用队列还是栈其实都行队列是 BFS 的感觉栈是 DFS 的感觉关键是成对取出、镜像配对放回这个约束不变。Python 里用deque而不是 list因为deque.popleft()是 O(1)而list.pop(0)是 O(n)性能差一个量级。这个细节在刷题时可能无所谓但工程上写代码我会一直保持这个习惯。3. 手把手写出两种 AC 解法3.1 先准备测试用例在刷题平台提交之前建议先在本地跑几个用例。先定义 TreeNode然后手工构造几棵树来验证。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right rightLeetCode 环境里 TreeNode 是现成的本地练习需要自己写一遍。手边最快的方式是直接按照结构一层层 new 出来比如构造一个对称树def build_symmetric_tree(): n3 TreeNode(3) n4 TreeNode(4) n4m TreeNode(4) n3m TreeNode(3) n2 TreeNode(2, n3, n4) n2m TreeNode(2, n4m, n3m) return TreeNode(1, n2, n2m)建议至少准备四类用例空树、单节点、形状不对称但值恰好回文的树、深层链式树。深层链式树主要用来测试迭代版对比递归版的空间表现面试时提到这一点会很加分。3.2 递归版代码与逐行讲解递归版是这道题最自然的解法完整代码如下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, p: TreeNode, q: 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 self._is_mirror(p.left, q.right) and self._is_mirror(p.right, q.left)逐行看入口函数isSymmetric只负责两件事空树返回 true否则把左右子树交给辅助函数。辅助函数_is_mirror才是真正干活的。前两个 if 处理空指针情况第三个 if 处理值不等的情况。最后一行是递归的核心p.left和q.right一组p.right和q.left一组这个交叉必须写对。Python 的and是短路求值。如果第一组_is_mirror(p.left, q.right)已经返回 false那第二组根本不会执行函数会立刻返回 false。这个特性对树这类找到一个反例就能提前结束的问题非常友好。用前面那棵对称树来推演一下isSymmetric(root)会调用_is_mirror(2, 2)接着比较_is_mirror(3, 3)和_is_mirror(4, 4)。注意这里比较的分别是左子树的左孩子和右子树的右孩子、左子树的右孩子和右子树的左孩子如果写成了左对左、右对右那判断的就是相同的树而不是对称的树了。3.3 迭代版代码与逐行讲解迭代版的核心是队列完整代码如下from collections import deque class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True queue deque([root.left, root.right]) while queue: p queue.popleft() q queue.popleft() if not p and not q: continue if not p or not q or p.val ! q.val: return False queue.append(p.left) queue.append(q.right) queue.append(p.right) queue.append(q.left) return True这里最需要理解的是入队顺序。每次取出两个节点后我们按照镜像关系把它们的下一层放进去先放 p.left 和 q.right再放 p.right 和 q.left。因为队列是先进先出所以下一次取出的恰好又是一对镜像节点。如果你把入队顺序写成p.left, q.left, p.right, q.right那整个算法就从判断镜像退化成了判断相同子树。这种错误视觉上很难发现因为代码结构完全一样只是顺序改了一下。我自己的排查技巧是找一棵三层的树在纸上手动推演队列的进出很快就能定位问题。不要在脑子里空想画出来最快。如果想改成栈只需要把popleft()换成pop()逻辑完全一致。面试时说出队列和栈都可以只是遍历顺序不同这个点显得你理解比背答案高一个层次。3.4 复杂度推导与面试话术复杂度分析是面试必问这里我给出完整的推导思路。时间复杂度整棵树的每个节点最多被访问一次因为每一对节点只比较一次节点总数是 n所以时间复杂度是 O(n)。空间复杂度要分情况说递归版空间消耗在调用栈上栈的深度等于树高 h。最坏情况是树退化成一条链h n空间 O(n)。平衡二叉树情况下满二叉树有 n 2^(h1) - 1所以 h log2(n1) - 1空间 O(log n)。迭代版空间消耗在队列上队列里最多同时存放某一层的所有节点。最坏情况是完全二叉树最后一层大约有 (n1)/2 个节点所以空间也是 O(n)。不过它不受递归深度限制树特别深时更稳妥。我一般会在面试里这样说递归版时间 O(n)空间 O(h)h 是树高最坏 O(n)迭代版时间 O(n)空间 O(n) 量级但避免了递归栈溢出的风险。如果是一棵可能很深的树我倾向于选迭代版。4. 我踩过的坑与排查技巧4.1 误区一只判断左右子树各自对称这是我第一次提交犯的错误代码写成这样class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True return self.isSymmetric(root.left) and self.isSymmetric(root.right)看起来好像也没什么问题左边是对称的右边也是对称的那整棵树不就对称吗实际上这是错的。这个判据只说明左右子树各自拥有对称结构完全没有比较左右子树之间是否存在镜像关系。我给你一个反例左子树是一棵教科书式对称树右子树也是一棵教科书式对称树但两者整体并不对称。比如左子树左下角挂着 4右子树右下角挂着 6这两个位置本应是镜像对应的却对不上而左子树、右子树自己看都是对称的。放到代码里isSymmetric(root.left)和isSymmetric(root.right)都返回 true整体却 false。所以这道题必须引入比较两棵子树的辅助函数不能只递归地调用 isSymmetric 自己。判断一棵树的整体对称本质上不是两个独立子问题的叠加而是一次跨子树的联合判断。4.2 误区二空节点判断顺序出错看这个错误版本def _is_mirror(self, p, q): if p.val ! q.val: return False if not p and not q: return True ...第一行就会炸。因为 p 完全可能是 NoneNone 没有 val 属性。在 Python 里会抛AttributeError: NoneType object has no attribute val在 Java/C 里对应 NullPointerException。正确的顺序是先把空值的几种情况全部排除再访问值属性。这也是我写任何二叉树递归函数都遵守的习惯先处理空指针再做值比较最后递归推进。顺序不对程序跑起来就是各种隐蔽的边界报错。还有一个小细节有人喜欢写紧凑版if not p or not q: return p is q这里必须用is而不是。因为可能触发对象的重载比较逻辑而我们这里想确认的仅仅是两个引用都是 None。4.3 误区三迭代入队顺序写错迭代版代码里入队顺序是p.left, q.right, p.right, q.left但很多人会顺手写成p.left, q.left, p.right, q.right。前者是比较镜像后者是比较相同。当初我就是这么写错的debug 了很久。问题在于相同子树的判断在恰好所有节点值都对称的样例上也可能通过一部分但在真正不对称的样例上就会暴露。比如一棵树左右子树完全相同但交叉位置不匹配按相同位置比较会一路相等最后错误地返回 true而正确答案是 false。排查方法很简单构造一棵三层的小树手动走一遍队列。用文字推演可能有点抽象但在纸上画两支箭头箭头一端是p.left另一端必须指到q.right画完你永远不会再写错。4.4 层序遍历回文陷阱与速查表还有一种思路很诱人既然对称那把树做层序遍历每一层序列应该都是回文。这个判断在不省略空节点的前提下是正确的但一旦省略空节点就会误判。举个例子1 / \ 2 2 \ \ 3 3不带空节点的层序结果是第一层 [1]第二层 [2,2]第三层 [3,3]。三个序列看起来都是回文但这棵树并不对称。因为左子树的 3 出现在右侧右子树的 3 也出现在右侧两个节点都在内侧镜像关系就不成立。如果把空节点也作为占位符第二层就变成 [2,2]第三层变成 [null,3,null,3]立刻就能看出不是回文。所以层序回文方案可以成立但实现时必须带着 null 占位还得分层处理复杂度比递归和迭代都高。我建议把它作为一道独立的小练习理解原理真正面试做题还是优先递归和迭代。最后整理一份速查表方便排查症状可能原因修复方式左右孩子值都对但整体误判比较方向写成了左对左、右对右改成交叉比较p.left 对 q.right空树返回 false入口边界写错if not root: return True深树栈溢出或递归超时递归深度过大改用队列/栈迭代版层序每层回文但整体不对称空节点未占位不要用层序方案或严格带 null 占位空节点报 AttributeError / NullPointerException终止条件顺序不对先判断是否为空再访问 val5. 面试现场与延伸思考5.1 三步讲法让面试官点头这道题在面试里出现频率很高我建议按三步来讲整体非常有条理。第一步确认边界。开口先问空树我们按 true 处理对吧这样单节点树也会自然返回 true。 这句话一出来面试官就知道你考虑问题全面。第二步画递归公式。直接在纸上写核心转换把一棵树拆成两棵子树isMirror(p, q) p.val q.val isMirror(p.left, q.right) isMirror(p.right, q.left)。配合一个小例子画两三层树把交叉箭头标出来。第三步主动补复杂度并给出迭代方案。可以说时间 O(n)递归空间 O(h)最坏 O(n)。为了避免递归栈溢出我可以改成队列迭代实现空间 O(n)。 主动送迭代版比等面试官追问效果好得多。我还在实际面试中遇到过一次追问如果树是一条深度一万的链递归会不会有问题这时候直接说我会用迭代版队列内存的节点数是有限的不会撑爆调用栈基本就稳了。5.2 关联题目与扩展方向这道题最值得做的关联题有两道LeetCode 100 相同的树以及 LeetCode 226 翻转二叉树。把三题放一起看你会发现比较两棵树是一个可复用的模板只是比较方向不同。100 题是直比101 题是交叉比226 题是改造结构。刷完这三题二叉树递归的基本功会扎实很多。往深了想这类镜像比较思想还能扩展到工程场景。例如某种配置树要求左右分支结构对称或者表达式树需要校验左右运算树结构是否镜像相容。虽然实际业务里直接要求树对称并不常见但如何把两个结构之间的关系拆成递归式这种方法论在很多嵌套数据结构校验里都能派上用场。如果你想在面试中展示超出平均水平的理解还可以提一句对称二叉树可以通过 Morris 遍历优化到 O(1) 空间只不过实现复杂工程必要性不大。点到为止即可不用展开因为面试官大概率也只是想听你会不会。我自己刷这道题最大的收获不是记住镜像配对公式而是养成了一套写递归树的习惯先列终止条件再决定递归参数怎么传最后才是返回值。后来遇到 LeetCode 100、226甚至一些回溯类问题这个习惯都帮我少踩了很多坑。顺便说一句如果你第一次写迭代版强烈建议在纸上手动走一遍队列的进出我当时就是因为没走把 right 和 left 的顺序写反白白 debug 了快二十分钟。对称二叉树这道题不大但值得慢慢品。
刷 LeetCode 的人大概率会在二叉树专题里撞上这道题——判断对称二叉树题号 101英文名 Symmetric Tree。它不是那种一眼就让人发怵的难题但特别有代表性一道题同时考了递归设计、树的结构认知和边界条件处理。我第一次做的时候以为只要分别判断左右子树对称就行结果提交之后被用例教育了。今天这篇文章就把这道题拆开揉碎从题目到底在问什么到递归和迭代两种通解再到我实际踩过的几个坑一次讲清楚。无论你是正在准备算法面试的开发者还是刚系统学二叉树数据结构的初学者看完之后应该都能把对称这两个字真正翻译成代码。你可能已经在各种刷题清单里见过它也知道答案大概长什么样但很多时候只是背会了并没有真正理解为什么这么写。这也是我写这篇的原因与其对着答案默写不如把背后的镜像关系、递归终止条件、队列配对方式都弄明白。后面我还会提到空树、单节点、链式树这些边界场景很多面试官就喜欢在这些小地方挖坑。1. 先搞懂题目到底在问什么1.1 定义什么叫作对称直观来说对称二叉树就是一棵树以根节点所在的中轴线为轴左右两边是镜像的。比如下面这棵树1 / \ 2 2 / \ / \ 3 4 4 3左子树和右子树从根节点 1 往下看是互相照镜子的关系左子树的左侧 3对应右子树的右侧 3左子树的右侧 4对应右子树的左侧 4。你把它想象成一个人站在镜子前左手对应镜中的右手右手对应镜中的左手。判断对称本质上就是在验证左子树和右子树互为镜像。很多人第一次会把对称和相等混在一起。相等是左边一棵树和右边一棵树完全一样对称则要求交叉位置一样。给你一个反例稍微改一下就能看出差别1 / \ 2 2 / \ / \ 3 4 3 4这棵树的左右子树其实是完全相同的但它并不对称因为左下角的 3 应该对应右下角的 4现在却对应到了 3。这就是交叉比较和相同位置比较的本质区别。1.2 对称、相同、翻转三者关系刷到这道题的时候很多教程会顺便提到另外两题LeetCode 100 相同的树以及 LeetCode 226 翻转二叉树。这三题放在一起对比着看会非常清楚。题目核心问题比较方式100. 相同的树两棵树是否完全一样p.left 与 q.left 比p.right 与 q.right 比226. 翻转二叉树把一棵树所有左右子树交换不比较只负责修改结构101. 对称二叉树一棵树自己是否镜像对称左子树的左孩子与右子树的右孩子比左子树的右孩子与右子树的左孩子比这里有一个全文最核心的公式。判断一棵树是否对称等价于判断 root.left 和 root.right 是否互为镜像可以写成isMirror(p, q) (p.val q.val) isMirror(p.left, q.right) isMirror(p.right, q.left)看到这个公式你大概就能明白为什么这道题和相同的树几乎共享同一套递归模板只是比较方向从直比变成了交叉比。另外还有一种等价思路先把树翻转再和原树比较是否相同。这种思路在理解上很有帮助但要注意别直接修改原树要么复制一份要么在递归参数里做虚拟翻转。面试时能主动提到这个等价关系往往是加分项。1.3 边界约定空树对称吗LeetCode 的判定是空树返回 true。很多人第一次写会在 isSymmetric 入口直接按if not root: return True处理也有人觉得空树没有对称性应该返回 false。但刷题平台的标准答案就是空树对称逻辑上也说得通空树没有左右子树自然不存在不对称的节点对。面试时最好主动问一句空树怎么算一般都会按 true 处理你确认一下反而显得严谨。至于单节点树root.left 和 root.right 都是 None辅助函数isMirror(None, None)会返回 true所以单节点天然对称。这两个边界在递归终止条件里其实已经天然涵盖了不需要在入口额外处理单节点的情况。2. 把镜像翻译成递归逻辑2.1 核心转换比较的对象是两棵子树写这道题最容易卡住的地方是不知道该拿谁和谁比。很多人第一反应是判断一个节点的左右孩子是否相等马上发现自己根本写不下去。原因在于对称是一个全局性质只盯着一个节点看是看不出来的。递归的精髓就是把一棵树的问题转化为两个子树的问题。既然是对称那比较对象就天然是两个节点。1 / \ L R在 L 和 R 的下一层镜像对应关系是L.left 对应 R.rightL.right 对应 R.left。为什么是交叉的你想象镜子立在 L 和 R 之间。L 的左外侧是整棵树的左外侧它在镜子里应该对应到 R 的右外侧也就是 R.right。同理L 的右内侧对应 R 的左内侧。所以才有isMirror(p.left, q.right)这种看起来有点拗口的写法它不是笔误而是镜像关系的直接翻译。2.2 递归函数的三个终止条件递归函数isMirror(p, q)的逻辑可以分为四步前三个是终止条件最后是递归推进如果 p 和 q 都是空返回 true。两棵空子树当然是镜像的。如果 p 和 q 中只有一个为空返回 false。一棵有节点、一棵没有节点结构已经不一样了。如果 p.val 和 q.val 不相等返回 false。继续递归比较 p.left 与 q.right以及 p.right 与 q.left两个结果都要成立。这里极其重要的是顺序。必须先处理空值再去访问 val。如果一上来就写if p.val ! q.val而 p 恰好是 None程序会直接抛空指针异常。这个顺序问题我在第四节还会展开说因为它是新手最容易踩的坑。有经验的开发者可能会写更紧凑的版本if not p or not q: return p is q用p is q判断两个对象是否同为 None。这种写法没问题但初学者建议还是拆成两行可读性更高也不容易出错。2.3 迭代解法的队列设计递归写完之后面试官经常追问一句如果不让用递归你怎么实现 这时候就需要迭代解法。迭代解法不需要调用栈而是用一个队列显式地维护待比较的节点对。核心思路是每次从队列里取出两个节点比较它们的值然后按镜像位置把它们的下一层节点成对放回去。具体来说初始化队列把 root.left 和 root.right 作为第一对放进去。循环直到队列为空。每次取出两个节点 p 和 q。如果 p 和 q 都是空继续下一轮。如果 p、q 中有一个为空或者值不相等直接返回 false。把 p.left 和 q.right 放进去再把 p.right 和 q.left 放进去。这里用队列还是栈其实都行队列是 BFS 的感觉栈是 DFS 的感觉关键是成对取出、镜像配对放回这个约束不变。Python 里用deque而不是 list因为deque.popleft()是 O(1)而list.pop(0)是 O(n)性能差一个量级。这个细节在刷题时可能无所谓但工程上写代码我会一直保持这个习惯。3. 手把手写出两种 AC 解法3.1 先准备测试用例在刷题平台提交之前建议先在本地跑几个用例。先定义 TreeNode然后手工构造几棵树来验证。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right rightLeetCode 环境里 TreeNode 是现成的本地练习需要自己写一遍。手边最快的方式是直接按照结构一层层 new 出来比如构造一个对称树def build_symmetric_tree(): n3 TreeNode(3) n4 TreeNode(4) n4m TreeNode(4) n3m TreeNode(3) n2 TreeNode(2, n3, n4) n2m TreeNode(2, n4m, n3m) return TreeNode(1, n2, n2m)建议至少准备四类用例空树、单节点、形状不对称但值恰好回文的树、深层链式树。深层链式树主要用来测试迭代版对比递归版的空间表现面试时提到这一点会很加分。3.2 递归版代码与逐行讲解递归版是这道题最自然的解法完整代码如下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, p: TreeNode, q: 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 self._is_mirror(p.left, q.right) and self._is_mirror(p.right, q.left)逐行看入口函数isSymmetric只负责两件事空树返回 true否则把左右子树交给辅助函数。辅助函数_is_mirror才是真正干活的。前两个 if 处理空指针情况第三个 if 处理值不等的情况。最后一行是递归的核心p.left和q.right一组p.right和q.left一组这个交叉必须写对。Python 的and是短路求值。如果第一组_is_mirror(p.left, q.right)已经返回 false那第二组根本不会执行函数会立刻返回 false。这个特性对树这类找到一个反例就能提前结束的问题非常友好。用前面那棵对称树来推演一下isSymmetric(root)会调用_is_mirror(2, 2)接着比较_is_mirror(3, 3)和_is_mirror(4, 4)。注意这里比较的分别是左子树的左孩子和右子树的右孩子、左子树的右孩子和右子树的左孩子如果写成了左对左、右对右那判断的就是相同的树而不是对称的树了。3.3 迭代版代码与逐行讲解迭代版的核心是队列完整代码如下from collections import deque class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True queue deque([root.left, root.right]) while queue: p queue.popleft() q queue.popleft() if not p and not q: continue if not p or not q or p.val ! q.val: return False queue.append(p.left) queue.append(q.right) queue.append(p.right) queue.append(q.left) return True这里最需要理解的是入队顺序。每次取出两个节点后我们按照镜像关系把它们的下一层放进去先放 p.left 和 q.right再放 p.right 和 q.left。因为队列是先进先出所以下一次取出的恰好又是一对镜像节点。如果你把入队顺序写成p.left, q.left, p.right, q.right那整个算法就从判断镜像退化成了判断相同子树。这种错误视觉上很难发现因为代码结构完全一样只是顺序改了一下。我自己的排查技巧是找一棵三层的树在纸上手动推演队列的进出很快就能定位问题。不要在脑子里空想画出来最快。如果想改成栈只需要把popleft()换成pop()逻辑完全一致。面试时说出队列和栈都可以只是遍历顺序不同这个点显得你理解比背答案高一个层次。3.4 复杂度推导与面试话术复杂度分析是面试必问这里我给出完整的推导思路。时间复杂度整棵树的每个节点最多被访问一次因为每一对节点只比较一次节点总数是 n所以时间复杂度是 O(n)。空间复杂度要分情况说递归版空间消耗在调用栈上栈的深度等于树高 h。最坏情况是树退化成一条链h n空间 O(n)。平衡二叉树情况下满二叉树有 n 2^(h1) - 1所以 h log2(n1) - 1空间 O(log n)。迭代版空间消耗在队列上队列里最多同时存放某一层的所有节点。最坏情况是完全二叉树最后一层大约有 (n1)/2 个节点所以空间也是 O(n)。不过它不受递归深度限制树特别深时更稳妥。我一般会在面试里这样说递归版时间 O(n)空间 O(h)h 是树高最坏 O(n)迭代版时间 O(n)空间 O(n) 量级但避免了递归栈溢出的风险。如果是一棵可能很深的树我倾向于选迭代版。4. 我踩过的坑与排查技巧4.1 误区一只判断左右子树各自对称这是我第一次提交犯的错误代码写成这样class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True return self.isSymmetric(root.left) and self.isSymmetric(root.right)看起来好像也没什么问题左边是对称的右边也是对称的那整棵树不就对称吗实际上这是错的。这个判据只说明左右子树各自拥有对称结构完全没有比较左右子树之间是否存在镜像关系。我给你一个反例左子树是一棵教科书式对称树右子树也是一棵教科书式对称树但两者整体并不对称。比如左子树左下角挂着 4右子树右下角挂着 6这两个位置本应是镜像对应的却对不上而左子树、右子树自己看都是对称的。放到代码里isSymmetric(root.left)和isSymmetric(root.right)都返回 true整体却 false。所以这道题必须引入比较两棵子树的辅助函数不能只递归地调用 isSymmetric 自己。判断一棵树的整体对称本质上不是两个独立子问题的叠加而是一次跨子树的联合判断。4.2 误区二空节点判断顺序出错看这个错误版本def _is_mirror(self, p, q): if p.val ! q.val: return False if not p and not q: return True ...第一行就会炸。因为 p 完全可能是 NoneNone 没有 val 属性。在 Python 里会抛AttributeError: NoneType object has no attribute val在 Java/C 里对应 NullPointerException。正确的顺序是先把空值的几种情况全部排除再访问值属性。这也是我写任何二叉树递归函数都遵守的习惯先处理空指针再做值比较最后递归推进。顺序不对程序跑起来就是各种隐蔽的边界报错。还有一个小细节有人喜欢写紧凑版if not p or not q: return p is q这里必须用is而不是。因为可能触发对象的重载比较逻辑而我们这里想确认的仅仅是两个引用都是 None。4.3 误区三迭代入队顺序写错迭代版代码里入队顺序是p.left, q.right, p.right, q.left但很多人会顺手写成p.left, q.left, p.right, q.right。前者是比较镜像后者是比较相同。当初我就是这么写错的debug 了很久。问题在于相同子树的判断在恰好所有节点值都对称的样例上也可能通过一部分但在真正不对称的样例上就会暴露。比如一棵树左右子树完全相同但交叉位置不匹配按相同位置比较会一路相等最后错误地返回 true而正确答案是 false。排查方法很简单构造一棵三层的小树手动走一遍队列。用文字推演可能有点抽象但在纸上画两支箭头箭头一端是p.left另一端必须指到q.right画完你永远不会再写错。4.4 层序遍历回文陷阱与速查表还有一种思路很诱人既然对称那把树做层序遍历每一层序列应该都是回文。这个判断在不省略空节点的前提下是正确的但一旦省略空节点就会误判。举个例子1 / \ 2 2 \ \ 3 3不带空节点的层序结果是第一层 [1]第二层 [2,2]第三层 [3,3]。三个序列看起来都是回文但这棵树并不对称。因为左子树的 3 出现在右侧右子树的 3 也出现在右侧两个节点都在内侧镜像关系就不成立。如果把空节点也作为占位符第二层就变成 [2,2]第三层变成 [null,3,null,3]立刻就能看出不是回文。所以层序回文方案可以成立但实现时必须带着 null 占位还得分层处理复杂度比递归和迭代都高。我建议把它作为一道独立的小练习理解原理真正面试做题还是优先递归和迭代。最后整理一份速查表方便排查症状可能原因修复方式左右孩子值都对但整体误判比较方向写成了左对左、右对右改成交叉比较p.left 对 q.right空树返回 false入口边界写错if not root: return True深树栈溢出或递归超时递归深度过大改用队列/栈迭代版层序每层回文但整体不对称空节点未占位不要用层序方案或严格带 null 占位空节点报 AttributeError / NullPointerException终止条件顺序不对先判断是否为空再访问 val5. 面试现场与延伸思考5.1 三步讲法让面试官点头这道题在面试里出现频率很高我建议按三步来讲整体非常有条理。第一步确认边界。开口先问空树我们按 true 处理对吧这样单节点树也会自然返回 true。 这句话一出来面试官就知道你考虑问题全面。第二步画递归公式。直接在纸上写核心转换把一棵树拆成两棵子树isMirror(p, q) p.val q.val isMirror(p.left, q.right) isMirror(p.right, q.left)。配合一个小例子画两三层树把交叉箭头标出来。第三步主动补复杂度并给出迭代方案。可以说时间 O(n)递归空间 O(h)最坏 O(n)。为了避免递归栈溢出我可以改成队列迭代实现空间 O(n)。 主动送迭代版比等面试官追问效果好得多。我还在实际面试中遇到过一次追问如果树是一条深度一万的链递归会不会有问题这时候直接说我会用迭代版队列内存的节点数是有限的不会撑爆调用栈基本就稳了。5.2 关联题目与扩展方向这道题最值得做的关联题有两道LeetCode 100 相同的树以及 LeetCode 226 翻转二叉树。把三题放一起看你会发现比较两棵树是一个可复用的模板只是比较方向不同。100 题是直比101 题是交叉比226 题是改造结构。刷完这三题二叉树递归的基本功会扎实很多。往深了想这类镜像比较思想还能扩展到工程场景。例如某种配置树要求左右分支结构对称或者表达式树需要校验左右运算树结构是否镜像相容。虽然实际业务里直接要求树对称并不常见但如何把两个结构之间的关系拆成递归式这种方法论在很多嵌套数据结构校验里都能派上用场。如果你想在面试中展示超出平均水平的理解还可以提一句对称二叉树可以通过 Morris 遍历优化到 O(1) 空间只不过实现复杂工程必要性不大。点到为止即可不用展开因为面试官大概率也只是想听你会不会。我自己刷这道题最大的收获不是记住镜像配对公式而是养成了一套写递归树的习惯先列终止条件再决定递归参数怎么传最后才是返回值。后来遇到 LeetCode 100、226甚至一些回溯类问题这个习惯都帮我少踩了很多坑。顺便说一句如果你第一次写迭代版强烈建议在纸上手动走一遍队列的进出我当时就是因为没走把 right 和 left 的顺序写反白白 debug 了快二十分钟。对称二叉树这道题不大但值得慢慢品。
