对称二叉树这道题我在LeetCode上刷了不下三遍每次以为彻底搞懂了过一阵子再看代码又会发现一个新的理解角度。101这个题号在二叉树专题里属于那种看起来人畜无害实际上很考验递归思维的题目面试高频程度直追反转链表。今天这篇刷题笔记我不打算只贴一段AC代码就完事而是把这道题从题目定义、递归本质、迭代实现、常见误区和延伸题目一次说透希望能给正在刷树的朋友一些可复现的思考路径。1. 先从题目本身说起对称到底在比什么1.1 对称不是左右子树长得一样很多人第一次看到这道题下意识会觉得判断二叉树对称不就是比较左子树和右子树是不是相等嘛这个理解是不准确的。来看一个最基本的反例1 / \ 2 2 / \ / \ 3 4 4 3这棵树是轴对称的但左子树是2-3,4右子树是2-4,3。如果按左子树等于右子树去比较3和4对不上直接就判定不对称了——正确答案却是对称。所以比较的不是左子树本身和右子树本身而是左子树的左孩子和右子树的右孩子比左子树的右孩子和右子树的左孩子比。这个镜像关系画个箭头就很清楚比较指针从根节点出发后一路都是左对右、右对左地交叉走。顺着这个思路代码的递归结构其实就已经浮出水面了。1.2 空节点是这题的第一个分水岭树里面空节点怎么处理是所有二叉树题目的基本功但这道题尤其敏感。考虑三种边界情况场景结果整棵树为空对称返回true根节点只有一个孩子不对称返回false左孩子空、右孩子非空或反之不对称返回false两个孩子都空对称返回true前两种情况往往被新手忽略。很多第一次写的代码直接拿根节点的左右孩子开始比没处理root nullptr的情况一提交就是空指针报错。LeetCode的测试用例里一定包含空树这一点不要有侥幸心理。我的建议是写树相关的递归函数第一步永远先问自己传进来的这个节点能不能是空。能是空就要在最开头把空的情况处理掉。这个习惯能在后面很多题目里帮你省下大量debug时间。2. 递归解法把镜像翻译成代码2.1 递归的入参设计一次比较两个节点对称判断需要同时追踪两个节点——左边那个和右边那个它们互为镜像位置。所以递归函数的入参一定是两个指针而不是一个。这也是这题和判断两棵树是否相同最大的区别。isSameTree(p, q)比较的是p和q各自的孩子方向一致p的左孩子对q的左孩子p的右孩子对q的右孩子。而isMirror(p, q)比较的是交叉方向p的左孩子对q的右孩子p的右孩子对q的左孩子。理解到这个层面代码就只是把思路翻译成语法而已class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return isMirror(root-left, root-right); } bool isMirror(TreeNode* left, TreeNode* right) { if (left nullptr right nullptr) return true; if (left nullptr || right nullptr) return false; return (left-val right-val) isMirror(left-left, right-right) isMirror(left-right, right-left); } };注意这段代码里我刻意用了left和right作为形参名而不是p和q。原因是这两个参数在递归过程中并不是左子树和右子树这么宽泛的概念而是当前这一对镜像节点。名字起得准确读代码的人就不需要额外脑补。2.2 三个终止条件和一个递推关系刚才的isMirror函数终止条件一共有三个必须按顺序写两个节点都为空这一对镜像节点不存在但关系依然成立返回true其中一个为空结构不对称直接返回false两个都不为空但值不相等值不对称返回false这里有一个很多教程没讲透的细节为什么值不相等是终止条件而不是递推条件因为一旦值不等整棵子树就不可能是对称的没必要再往下递归这其实是一种剪枝。虽然写不写这个判断递归一定能结束但写了之后遇到不对称的树会提前返回实际运行中的平均性能会更好。递推关系则是isMirror(left, right) (left.val right.val) isMirror(left.left, right.right) isMirror(left.right, right.left)这个式子本身就说明了对称树的递归定义一棵树对称当且仅当它的左子树和右子树互为镜像而两棵树互为镜像当且仅当它们的根值相等且A的左子树与B的右子树互为镜像A的右子树与B的左子树互为镜像。2.3 复杂度分析和为什么递归最自然递归解法的时间复杂度是O(n)因为每个节点最多被访问一次。空间复杂度是O(h)h是树的高度最坏情况下树退化成链表h等于n递归栈会压到n层。LeetCode上一般不会因为递归深度为难你但如果遇到一个高度上万的长链条树递归解法确实存在爆栈风险这时候迭代解法就更稳妥。从工程角度说递归解法之所以是我推荐的第一方案不是因为它效率最高而是因为它和问题的数学定义一一对应。你不需要额外维护任何数据结构只需要相信两个递归调用会返回正确结果整个函数就自洽了。这种递归信仰是二叉树题目最核心的思维模式刷树一定要先过这一关。3. 迭代解法队列里交替出现的镜像节点3.1 层序思路的变体成对出队迭代解法的本质是用一个显式的容器模拟递归栈的调用过程。最直观的版本是用队列做广度优先遍历但不是一层一层地保存节点而是每次成对入队、成对出队。代码是这样class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; queueTreeNode* q; q.push(root-left); q.push(root-right); while (!q.empty()) { TreeNode* left q.front(); q.pop(); TreeNode* right q.front(); q.pop(); if (left nullptr right nullptr) continue; if (left nullptr || right nullptr) return false; if (left-val ! right-val) return false; q.push(left-left); q.push(right-right); q.push(left-right); q.push(right-left); } return true; } };这里有一个很多初学者不理解的地方为什么两个节点都为空时是continue而不是直接返回true因为队列里可能还有别的待比较节点对此时还不能下结论。只有整个队列为空所有镜像节点对都比较完毕才能说这棵树是对称的。这个细节区分了局部判断和全局判断。3.2 入队顺序是唯一会出错的地方迭代解法里最容易写错的就是入队顺序。我的记忆口诀是入队顺序和递归调用的顺序保持一致。递归代码里的顺序是isMirror(left-left, right-right) // 外侧对 isMirror(left-right, right-left) // 内侧对所以队列里入队的顺序应当先是left-left和right-right再是left-right和right-left。如果你把顺序颠倒写成left-left和left-right那么出队比较的节点对就不是镜像位置结果会完全错误但代码又不会报错只能靠测试用例去发现。为了彻底避免这个问题我更推荐一种打包写法不要分别push两个节点而是把这一对节点作为一个整体看待。不过LeetCode的TreeNode定义不允许你打包所以只能靠注释或者函数命名来提醒自己。我在代码里习惯把变量名写清楚left和right两个变量在每次循环里都代表一组待比较的镜像节点对一眼就能看出入队逻辑有没有写反。3.3 用栈写迭代的两个注意点队列版本已经够用了但有不少人会问用栈行不行答案是可以而且栈版本和队列版本几乎一样只是容器类型不同。把queue换成stack代码主体完全不用改。区别在于遍历顺序队列是广度优先式地比较栈是深度优先式地比较。两者都能覆盖整棵树因为对称性的判断不依赖比较顺序只要每一对镜像节点都被比较到就行。用栈的时候有两点需要注意第一出栈顺序不影响正确性但影响你调试时看到的中间状态。栈版本的中间态是先比较最深的镜像对用打印语句调bug时不如队列直观。第二如果对空间占用有强迫症可以在检测到两个节点都为空时直接continue而不是push空节点进去这样栈里永远不会出现空指针。上面的代码为了可读性选择了push空节点工程上稍微优化一下会更干净。4. 刷题过程中最容易踩的四个坑4.1 坑一把对称当成了相同这个坑我在1.1节已经点过名了但依然值得单独拿出来说因为它是思路层面的错误即使代码写得再熟练方向错了照样白搭。判断相同树的递归调用方向是左对左、右对右判断对称树的递归调用方向是左对右、右对左。肉眼看起来区别不大但反映到代码里就是isMirror(left-left, right-right)和isMirror(left-left, left-right)的差别。后者连参数来源都变了本质上是在同一棵左子树内部做比较当然不可能得到正确结果。如果你在LeetCode上提交后发现答案错误但测试用例前面的树都能过突然挂在某个多层的树上优先检查递归调用的方向是不是写成了左对左。4.2 坑二递归终止条件写岔了再来看一个错误示范bool isMirror(TreeNode* left, TreeNode* right) { if (left nullptr right nullptr) return true; if (left-val ! right-val) return false; // 如果left是空、right非空上一行直接空指针崩溃 return isMirror(left-left, right-right) isMirror(left-right, right-left); }这个写法错在left-val ! right-val这一行没有先排除其中一个为空的情况。只要left或right有一个是空指针访问-val就是未定义行为LeetCode上直接报Runtime Error。正确顺序是两个都空 - 返回true一个空一个非空 - 返回false两个都非空但不相等 - 返回false最后才进入递归。这个顺序不能乱尤其不能把判空放在字符串取值之后。4.3 坑三迭代版本层序错了还浑然不觉迭代版本如果入队顺序写错不会报错只是返回错误结果。这时候你可能会百思不得其解明明逻辑看起来都对为什么答案不对这里分享一个我自己常用的调试方法当树的规模较小、层数不超过3时直接把每一对出队节点的值或者用特殊符号表示空节点打印出来一眼就能看出来比较的配对方向是否正确。对称树的成对出队序列有非常明显的特征整个序列读起来是对称的。如果打印结果看起来没有对称性八成就是入队顺序的问题而不是比较逻辑的问题。4.4 坑四只拿示例用例验证就提交LeetCode给的示例通常比较温和但这道题你一定要额外测以下几种情况空树null 单节点1 两个节点的树1-2左没有右 三层不完全树根节点左右孩子都有但左孩子的右孩子为空、右孩子的左孩子为空 值不对称但结构对称的树1 / \ 2 2 / \ / \ 1 2 2 1尤其是值不对称但结构对称的情况能帮你确认判断逻辑里确实包含了val比较而不是只比了树形。直接拿这些用例去测比盲提交等WA再改要节省时间得多。5. 一题四吃的延展练习5.1 LeetCode 100从对称到全等LeetCode 100题是相同的树判断两棵二叉树是否完全相同。它的递归写法和isMirror只有一处不同递归调用方向变成isSame(left-left, right-left) isSame(left-right, right-right)。这两道题放在一起对比学习效果特别好。你会发现对称和相同在递归形式上就是交叉和平行的区别。把两道题的代码并排放在IDE里自己动手改一改参数方向对递归的理解会比单独刷十道题更深刻。5.2 LeetCode 226翻转二叉树后判断对称226题是翻转二叉树。翻转操作的本质是把每个节点的左右孩子互换。那么一个有趣的推论是一棵二叉树对称当且仅当它的左子树翻转后和右子树完全相同。这个等价关系用代码表述就是bool isSymmetric(TreeNode* root) { if (root nullptr) return true; TreeNode* flippedLeft invertTree(root-left); return isSameTree(flippedLeft, root-right); }当然实际刷题时不建议真的翻转整棵树再去比较额外引入O(n)的时间开销。但这个等价关系非常适合用来验证你自己对对称的理解是否到位——如果你能口算清楚为什么翻转后全等就等价于对称说明递归思维已经过关了。5.3 LeetCode 572子树问题里的模式复用572题是另一棵树的子树判断一棵树subRoot是否是主树root的子树。这题的标准解法之一就是遍历主树的每个节点用相同的树100题去比较。这里用到的比较逻辑和对称树的套路同源但是判断的是部分与整体的关系比对称更复杂一些。刷完101题后我很推荐马上去做572。因为你会自然地把如何遍历一个树的所有子树和如何比较两棵子树是否相同这两个问题拆开分别用层序遍历和递归解决。这种组合拳式的刷法对面试时的临场拆题非常有帮助。5.4 面试现场的展开话题对称二叉树在面试中很常见而且面试官特别喜欢在这道题后面追问能不能不用递归内存占用是多少如果树的节点值很多如何优化比较你能不能在O(1)额外空间下判断O(1)空间的版本通常用Morris遍历的思路但那是hard级别的延伸一般面试不会要求。不过你要能说清楚递归版本的栈空间复杂度是O(h)以及为什么最坏情况下会退化到O(n)这样已经足够展示基本功。另外这道题的镜像思想在工程里也有对应场景比如前端比较两个DOM树的对称性、后端校验配置文件的镜像结构、甚至数据校验里判断两个JSON对象是否镜像对称处理思路都是同一个递归框架。多想想题目和现实场景的连接刷题才不会刷成背答案。最后再说点实在的对称二叉树这道题我最大的体会是它验证的不是你背了多少模板而是你有没有真正理解递归函数自己调用自己时参数是怎么变化这件事。理解了这个判断对称、判断相同、判断子树本质都是同一套思维在换皮。我自己刷题有个习惯每道树的题目AC之后都会把递归调用方向的注释写在代码上方比如这里比较的是左子树的左孩子和右子树的右孩子。过两个月再翻代码不用重新推一遍逻辑扫一眼注释就全想起来了。如果你也在刷LeetCode不妨试试这个方法别嫌啰嗦真的很管用。