刚开始刷二叉树题的时候，我拿到“对称二叉树”这道题的第一反应是“判断每个节点左右孩子是否相等”。写完一跑，错得那叫一个干净利落。后来才想明白，对称二叉树的判断对象根本不是“左右孩子相等”，而是“左子树和右子树互为镜像”。这道题在力扣里的编号是101，用C语言写递归和迭代两种解法都很有代表性，尤其是迭代解法，能帮你把“怎么用队列维护比较顺序”这件事彻底想清楚。这篇我就用图解思路把两种解法从头到尾拆开讲，适合刚入门二叉树、准备面试手撕代码，或者想搞懂递归与迭代差异的读者。
先给结论：对称二叉树的核心只有一句话——一棵树的左子树，必须镜像对等于右子树。所谓“镜像对等”，不是简单的值相同，而是“左侧的最左对应右侧的最右，左侧的最右对应右侧的最左”。这个对应关系，就是递归和迭代两种解法的灵魂。
1. 审题：对称二叉树到底在判断什么
1.1 这句代码为什么是错的
很多人（包括当时的我）第一版代码会长这样：
bool isSymmetric(struct TreeNode* root) { if (root == NULL) return true; return root->left->val == root->right->val; }这连编译都过不了，因为根本没考虑root->left或者root->right本身可能是空指针的情况。就算你防御性地加了非空判断，也只能比较“根节点的左右孩子值是否相等”。但对称二叉树要的远远不止这一层：
1 / \ 2 2 / \ / \ 3 4 4 3上面这棵树，根节点的左右孩子都是2，但真正对称是靠下面“3对齐3，4对齐4”达成的。如果换成下面这样：
1 / \ 2 2 \ \ 3 3根节点左右孩子还是2和2，但它不对称，因为左子树的右孩子是3，右子树的右孩子是3，而左子树的左孩子为空，右子树的左孩子也为空。这怎么算对称？“左侧的最左是空，右侧的最右是空”，空对空确实相等；但“左侧的最右是3，右侧的最左是空”，3对空，不对称。所以只看根节点左右孩子，一定会漏掉深层信息。
1.2 镜像比较的三层判定逻辑
对称比较的对象，自始至终都是两个节点：把根节点的左子树和右子树看作一对，不断往下展开比较。
两个节点u和v要满足镜像条件，一共分三层：
| 判定层级 | 条件 | 结论 |
|---|---|---|
| 第一层 | u和v同时为空 | 对称，递归结束 |
| 第二层 | u和v一个为空一个非空 | 不对称，直接失败 |
| 第三层 | u和v值不同 | 不对称，直接失败 |
只有前两层都通过了，也就是两个节点都非空且值相同，才需要继续往下比较。
这时候最关键的问题来了：往下该比较谁的子树？答案是——u的左子树要比v的右子树，u的右子树要比v的左子树。这就是“镜像”二字的含义：我在这边的左边，到了镜子那边就变成右边。
用代码写判断逻辑就是：
if (u == NULL && v == NULL) return true; if (u == NULL || v == NULL) return false; if (u->val != v->val) return false; return isMirror(u->left, v->right) && isMirror(u->right, v->left);这道题所有解法，不管递归还是迭代，本质上都是在用各种方式落实这张三层判定表。谁把这个表背清楚，谁就掌握了这道题。
2. 递归解法：双参数设计的核心思路
2.1 为什么不是“一个节点递归自己”
我见过不少初学者的迷惑点：对称二叉树是一个树的问题，递归函数为什么不能只接收一个root节点？
你可以试着想一下：如果函数只接收一个节点，你能同时拿到它的左子树和右子树来比吗？拿得到，但只能比“这一层”。比完“左孩子对右孩子”之后，下一层要比较的是“左孩子的左孩子对右孩子的右孩子”，这时候函数只知道左孩子，不知道左孩子的兄弟长什么样。信息断档了。
所以这里真正的切入点不是“一棵树自己对称”，而是“两棵树互为镜像”。根节点的左子树和右子树，就是最先需要比较的“两棵树”。递归函数应该接收两个参数：一侧子树的节点，和另一侧对称位置上的节点。
2.2 递归函数的设计过程
先把主函数写出来，处理空树情况：
bool isSymmetric(struct TreeNode* root) { if (root == NULL) return true; return isMirror(root->left, root->right); }空树算对称，这是个约定俗成的定义，力扣的测试用例也这么认为。
然后写关键的isMirror函数。这个函数的任务只有一个：判断传入的两个节点是否互为镜像。按照前面那张判定表逐层落实：
bool isMirror(struct TreeNode* left, struct TreeNode* right) { if (left == NULL && right == NULL) return true; if (left == NULL || right == NULL) return false; if (left->val != right->val) return false; return isMirror(left->left, right->right) && isMirror(left->right, right->left); }这里每一行的顺序都不能乱。先判“同时为空”，再判“一个为空”，最后才敢访问left->val。如果把判空放到值比较后面，空指针访问就崩了。
最后用短路运算符&&连接两次递归调用。C语言的短路特性天然保证了：如果左边的镜像判断已经失败，右边的递归根本不会执行，这既省时间，也避免了一些无意义的递归调用。
2.3 C语言完整代码示例
把上面的函数整合成一道可以直接提交的题解：
bool isMirror(struct TreeNode* left, struct TreeNode* right) { if (left == NULL && right == NULL) return true; if (left == NULL || right == NULL) return false; if (left->val != right->val) return false; return isMirror(left->left, right->right) && isMirror(left->right, right->left); } bool isSymmetric(struct TreeNode* root) { if (root == NULL) return true; return isMirror(root->left, root->right); }整体代码大概十行出头，跟层序遍历的模板结构完全不一样。递归解法的好处是：代码和数学定义一一对应，写出来几乎不可能错，适合作为面试时的第一版答案。
3. 图解递归：调用过程逐层展开
3.1 一棵对称树的完整递归调用过程
空谈“镜像比较”容易晕，我画一棵对称树来走一遍递归：
1 / \ 2 2 / \ / \ 3 4 4 3从主函数开始，isMirror(root->left, root->right)实际上是isMirror(2, 2)。进入函数后，两个节点都不是空指针，值又都是2，于是递归两次：
- 第一次：
isMirror(2->left, 2->right)，即isMirror(3, 3) - 第二次：
isMirror(2->right, 2->left)，即isMirror(4, 4)
isMirror(3, 3)展开：两个3都不是空，值相等，继续往下一层，比较isMirror(3->left, 3->right)也就是isMirror(NULL, NULL)，和isMirror(3->right, 3->left)也就是isMirror(NULL, NULL)。两边都是“同时为空”，返回true。isMirror(3, 3)的结果是true && true = true。
isMirror(4, 4)同理，两边都到达空节点，返回true。
最外层的isMirror(2, 2)结果就是true && true = true，整棵树对称，返回true。
整个递归调用链可以用缩进图表示：
isMirror(2, 2) ├── isMirror(2.left=3, 2.right=3) │ ├── isMirror(3.left=NULL, 3.right=NULL) → true │ └── isMirror(3.right=NULL, 3.left=NULL) → true ├── 结果为 true && true = true ├── isMirror(2.right=4, 2.left=4) │ ├── isMirror(4.left=NULL, 4.right=NULL) → true │ └── isMirror(4.right=NULL, 4.left=NULL) → true ├── 结果为 true && true = true └── 最终结果为 true && true = true注意看第二层递归的参数顺序：左子树的左孩子，对应右子树的右孩子；左子树的右孩子，对应右子树的左孩子。一步都没有走错。
3.2 不对称的树在哪个位置暴露问题
再看一棵不对称的树：
1 / \ 2 2 / / 3 3这棵树的问题是：左子树有左孩子3，右子树的左孩子也是3，但左子树没有右孩子，右子树也没有右孩子。严格按镜像规则，左子树的左孩子3应该对应右子树的右孩子（空），这一层就直接失败。
流程是这样的：isMirror(2, 2)进入第三层，递归到isMirror(2->left=3, 2->right=NULL)。左边非空右边空，命中“一个为空一个非空”的判定，返回false。因为&&短路，后面的isMirror(2->right, 2->left)不会执行，整个函数直接返回false。
这里值得特别注意的是：如果一个人满脑子想的都是“左右相等”，他会去比较“左孩子的左孩子”和“右孩子的左孩子”，也就是isMirror(3, 3)。一旦这么写了，这棵不对称的树就会被误判成对称。所以还是那句话，递归参数里的left->left对right->right、left->right对right->left是这道题唯一的正确写序，错一个字母全盘皆输。
3.3 递归边界与回溯的对应关系
递归调用一旦深入到空节点，就是回溯开始的信号。比如isMirror(3->left, 3->right)两个都是空，函数返回true，这代表“从这一层往下看，没有更多内容了，两边都探到底了，一致”。
可以把空节点理解成“触底”。每次触底返回true，上一层拿到两个true之后，通过&&汇总成自己的结果，再继续向上返回。整个过程是一个自底向上的汇总过程，跟“后序遍历”的思想有点像——先算完子树结果，再算当前节点结果。
理解这个模式有个实际好处：面试时候如果被追问“递归会不会栈溢出”，你至少知道答案——树的高度就是递归深度。完全二叉树高度是O(log n)，但退化成链状的树高度是O(n)，会把递归栈打爆。这就引出了迭代解法的必要性。
4. 迭代解法：循环队列与成对出队
4.1 为什么迭代解法能规避递归栈风险
递归版的isMirror深度等于树高。遇到一棵极度不平衡的树，比如每个节点只有右孩子，递归深度会堆到n，C语言默认的函数调用栈根本扛不住这么大的深度，直接段错误。这时候就需要用迭代解法，自己用数据结构模拟那个“比较队列”。
迭代思路其实跟 BFS 层序遍历很像，但是有一个决定性的区别：层序遍历每次只弹一个节点，对称判断每次要弹一对节点。队列里存储的单位不是单个节点，而是“待比较的节点对”。
4.2 镜像规则下的入队顺序
迭代解法的完整比较规则是：
- 根节点为空，直接返回
true。 - 先把
root->left和root->right这一对节点入队。 - 每次从队头弹出两个节点
u和v，执行前面那张三层判定表。 - 如果两个节点都非空且值相等，按镜像规则入队它们的子树：
u->left与v->right作为一对入队；u->right与v->left作为一对入队。
- 重复直到队列为空。队列清空且没有提前失败，就是对称。
为什么要这样配对入队？因为u和v处于镜像位置。想象你在照镜子：你抬左手，镜子里的你抬右手。子树的对应关系也遵循这个逻辑——u的左侧对应v的右侧，u的右侧对应v的左侧。队列把这种“成对的对应关系”排队等着比较，谁先谁后其实无所谓，但配对绝不能错。
4.3 C语言数组模拟循环队列
C语言没有C++的std::queue，所以得用数组模拟循环队列。二叉树的节点总数是有限的，每个节点最多入队一次，所以队列容量不用开很大，但至少要能容纳全部节点。我习惯开成2000，这个数字应对常规刷题测试足够了。
队列数据结构这样定义：
struct TreeNode* queue[2000]; int head = 0; int tail = 0;入队操作是queue[tail++] = node;，出队操作是struct TreeNode* node = queue[head++];。由于数组不会被“真正填满后再入队”（每个节点最多入队一次，总共最多n个节点），所以用简单的顺序队列就够，不需要真的去写循环取模。但如果你打算自己封装一个通用队列，或者测试数据特别大，那还是用(head + 1) % capacity的循环方式更稳妥。
4.4 迭代解法完整C语言代码
bool isSymmetric(struct TreeNode* root) { if (root == NULL) return true; struct TreeNode* queue[2000]; int head = 0; int tail = 0; queue[tail++] = root->left; queue[tail++] = root->right; while (head < tail) { struct TreeNode* u = queue[head++]; struct TreeNode* v = queue[head++]; if (u == NULL && v == NULL) continue; if (u == NULL || v == NULL) return false; if (u->val != v->val) return false; queue[tail++] = u->left; queue[tail++] = v->right; queue[tail++] = u->right; queue[tail++] = v->left; } return true; }这个版本最直观，所有节点都在一个队列里排队，弹出两个处理两个。代码跑起来的行为非常像 BFS，但又比 BFS 多了“镜像配对”的约束。
5. 图解迭代：队列状态变化全过程
5.1 队列变化的完整推演表
还是用这棵树：
1 / \ 2 2 / \ / \ 3 4 4 3逐步跟踪队列。为了清楚，我把每次弹出的节点和入队的节点列成一个表：
| 轮次 | 弹出一对 (u, v) | 判定结果 | 入队内容 |
|---|---|---|---|
| 1 | (2, 2) | 值相等，继续 | (3, 3), (4, 4) |
| 2 | (3, 3) | 值相等，继续 | (NULL, NULL), (NULL, NULL) |
| 3 | (4, 4) | 值相等，继续 | (NULL, NULL), (NULL, NULL) |
| 4 | (NULL, NULL) | 双方为空，continue | 无 |
| 5 | (NULL, NULL) | 双方为空，continue | 无 |
| 6 | (NULL, NULL) | 双方为空，continue | 无 |
| 7 | (NULL, NULL) | 双方为空，continue | 无 |
队列清空，返回true。
仔细观察会发现，第2轮入队了四个空指针，第3轮又入队四个空指针，加起来八个空指针四对，消耗了四轮。“空节点也要入队”这一点非常反直觉，很多第一次写迭代的人会跳过空节点不入队，结果程序在弹到一半的时候队列提前空掉，误判为对称。
5.2 为什么空节点必须入队
空节点是“比较到尽头”的信号。如果不把空节点入队，就会出现一种情况：一棵不对称的树，在某次比较时值相等，但它的子树一个是空一个是非空。你直接把非空的那个入队了，空的那个扔掉了，那么下一轮弹出的两个节点就变成“一对二”的错位比较，把它误判成对称。
举个例子：
1 / \ 2 2 / \ 3 3这棵树其实是对称的（3对应镜像位置的3），但如果你把空指针滤掉，左子树只有左孩子3，右子树只有右孩子3，队列弹出一对（3, 3），值相等，看似正确。但注意，如果换成：
1 / \ 2 2 / \ 3 4这棵树不对称，因为3不等于4，程序会正确返回false。真正危险的是下面这种情况：
1 / \ 2 2 / \ 3 3 \ / 4 4左子树右链的4，必须对应右子树左链的4；左子树左链的3，必须对应右子树右链的3。如果你把空指针滤掉，队列里的节点对就会错位，本来“3对应3，4对应4”的比较，可能变成“3对应4”，直接误判。所以千万不要图省事过滤空指针，保持成对比较的节奏是迭代算法的命根子。
5.3 迭代与递归的同一性
比较迭代版和递归版，你很快会发现一个事实：它们在做完全一样的事情。
- 递归的调用参数
(left->left, right->right)就是迭代里第一次入队的内容。 - 递归的调用参数
(left->right, right->left)就是迭代里第二次入队的内容。 - 递归的“空节点返回”就是迭代的“空节点continue”。
递归靠函数调用栈保存还没比较完的状态，迭代靠队列保存待比较状态。一个是隐式栈，一个是显式队列，底层逻辑是同构的。理解了这个同构关系，你就能在面试时候很自然地说出“递归和迭代本质上是一个思路的两种表达方式”。
6. C语言实现细节与常见坑
6.1 空指针判断的顺序不能乱
递归和迭代代码里都有三段式判定：
if (u == NULL && v == NULL) // 先判双空 if (u == NULL || v == NULL) // 再判单空 if (u->val != v->val) // 最后才取值比较三个顺序不能交换。如果先写u->val != v->val，当u是空指针时就是解引用空指针，程序直接崩溃。如果先写单空判断再写双空判断，两个都空的情况会被单空捕获并返回false，对空树对就会误判。这个顺序记成“先双空，再单空，最后比价值”就稳了。
6.2 队列容量应该开多大
迭代解法里我直接开了固定大小2000，这在大多数力扣测试里够用。但严谨一点说，队列里的节点数量在极端情况下会接近整棵树的节点总数n。最坏情况是满二叉树，最后一层有大约n/2个节点，每一对都要排进队列。
所以严谨的做法是用节点的总个数动态分配：
struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 2000);如果你对数据规模不确定，可以先把root的子树数量统计出来，再按需分配。不过刷题场景固定开2000已经能通过几乎所有用例，关键是写清楚为什么够用：每个节点最多入队一次，队列里的元素不会超过节点总数。
6.3 递归版本的栈空间
递归版每次调用isMirror都会消耗一小块函数栈空间。树的形状越接近链，递归深度越接近n，栈溢出风险越大。这也是迭代解法存在的最大价值。
如果面试官问“递归和迭代你选哪个”，最好的回答是：先给出递归版本，代码清晰、逻辑直观；然后主动补充一句“但最坏情况下递归深度等于树高，如果树不平衡，可能栈溢出，所以我更推荐迭代版”。这句话能展现你对复杂度边界的敏感度。
6.4 内存管理的提醒
力扣的C语言环境最终会回收内存，但如果你在实际工程或者本地测试里跑，别忘了释放动态分配的队列内存。用malloc分配的数组在函数返回前free(queue)一下，避免内存泄漏。递归版本不需要额外释放，因为它没有分配任何堆内存。
7. 复杂度对比与面试延伸
7.1 时间与空间复杂度计算
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归 | O(n) | O(h)，最坏O(n) | 代码清晰，适合面试首答 |
| 迭代 | O(n) | O(m)，m为队列最大长度，最坏O(n) | 规避栈溢出，适合树高很大的场景 |
时间复杂度都是O(n)，因为每个节点都只被访问一次。递归的空间复杂度取决于树高h：完全二叉树是O(log n)，链状树是O(n)。迭代队列的最大长度大约等于树某一层的最大节点数，满二叉树是O(n/2)，本质上也是O(n)。两者最坏情况空间复杂度一致，但迭代版的栈溢出风险更低。
7.2 镜像比较思维的可迁移性
对称二叉树的“镜像比较”思维能直接迁移到好几道题上：
- 判断两棵树是否相同：把
isMirror(u->left, v->right)改成isSame(u->left, v->left)，整体判定逻辑照抄。 - 翻转二叉树：交换每个节点的左右子树，本质上是在操作“镜像位置”。
- 判断一棵树是否含另一棵树的子树：用“比较两个树是否相同”的过程，配合树的遍历。
很多二叉树题目的内核都是“如何把两个树/两个节点正确地对应起来”，对称二叉树是理解这个概念的最佳入门题。搞懂了这道题，后续看“相同的树”“子树判断”这些题目，都会觉得顺很多。
7.3 面试追问的常见变体
面试官一般不会只满足于“你写出来了”。他可能会追问：
“如果给你一棵层序遍历的数组，怎么判断它是不是对称二叉树？”
这个问题其实已经帮你把树形结构拍平了。可以先把数组恢复成二叉树，再用上面的迭代解法；也可以直接在数组层面上判断：每一层从左往右的子数组和从右往左的子数组是否完全相同。后者代码更简洁，但需要你理解层序数组中父子节点的序号关系。
“能不能不用队列，用两个栈实现？”
可以。把队列的先进先出改成后进先出，配对逻辑完全不变。用两个栈分别存“左侧”和“右侧”，每次从两个栈顶各取一个节点做比较，然后按镜像规则把下一层压栈。这是一道经典的变体题，考察你对“用不同数据结构维护同样状态”的理解。
“如果树特别大，递归和迭代谁更稳？”
迭代更稳。原因前面已经说了，递归深度受树高限制，而链状树深可达到n。迭代的空间复杂度虽然最坏也是O(n)，但队列操作发生在堆区，比函数栈好控制得多。
关于这道题的最后一点体会
我在实际刷题中发现，真正导致一个人卡在“对称二叉树”上的，往往不是递归和迭代代码本身，而是最开始那句“左对右，右对左”的对应关系没想清楚。建议你拿到任何一道树相关的题目，先画一棵小树，把“谁和谁比”写在纸上，再写代码。这道题先画一棵对称树模拟一遍递归，再画一棵不对称树模拟一遍，两遍走完，代码基本就是默写。
递归版本十行左右，是面试的“安全牌”；迭代版本多十几行，是展示你掌握“用队列模拟比较过程”能力的加分项。两个版本都建议手写三遍以上，第一遍照着写，第二遍尝试不查资料，第三遍一边写一边随口解释每行代码的含义。能到第三遍的程度，面试考到这道题你就稳了。
