对称二叉树这道题，我在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; queue<TreeNode*> 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，不妨试试这个方法，别嫌啰嗦，真的很管用。
