刚开始刷二叉树题的时候我拿到“对称二叉树”这道题的第一反应是“判断每个节点左右孩子是否相等”。写完一跑错得那叫一个干净利落。后来才想明白对称二叉树的判断对象根本不是“左右孩子相等”而是“左子树和右子树互为镜像”。这道题在力扣里的编号是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对齐34对齐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.left3, 2.right3) │ ├── isMirror(3.leftNULL, 3.rightNULL) → true │ └── isMirror(3.rightNULL, 3.leftNULL) → true ├── 结果为 true true true ├── isMirror(2.right4, 2.left4) │ ├── isMirror(4.leftNULL, 4.rightNULL) → true │ └── isMirror(4.rightNULL, 4.leftNULL) → true ├── 结果为 true true true └── 最终结果为 true true true注意看第二层递归的参数顺序左子树的左孩子对应右子树的右孩子左子树的右孩子对应右子树的左孩子。一步都没有走错。3.2 不对称的树在哪个位置暴露问题再看一棵不对称的树1 / \ 2 2 / / 3 3这棵树的问题是左子树有左孩子3右子树的左孩子也是3但左子树没有右孩子右子树也没有右孩子。严格按镜像规则左子树的左孩子3应该对应右子树的右孩子空这一层就直接失败。流程是这样的isMirror(2, 2)进入第三层递归到isMirror(2-left3, 2-rightNULL)。左边非空右边空命中“一个为空一个非空”的判定返回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深度等于树高。遇到一棵极度不平衡的树比如每个节点只有右孩子递归深度会堆到nC语言默认的函数调用栈根本扛不住这么大的深度直接段错误。这时候就需要用迭代解法自己用数据结构模拟那个“比较队列”。迭代思路其实跟 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对应34对应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)但队列操作发生在堆区比函数栈好控制得多。关于这道题的最后一点体会我在实际刷题中发现真正导致一个人卡在“对称二叉树”上的往往不是递归和迭代代码本身而是最开始那句“左对右右对左”的对应关系没想清楚。建议你拿到任何一道树相关的题目先画一棵小树把“谁和谁比”写在纸上再写代码。这道题先画一棵对称树模拟一遍递归再画一棵不对称树模拟一遍两遍走完代码基本就是默写。递归版本十行左右是面试的“安全牌”迭代版本多十几行是展示你掌握“用队列模拟比较过程”能力的加分项。两个版本都建议手写三遍以上第一遍照着写第二遍尝试不查资料第三遍一边写一边随口解释每行代码的含义。能到第三遍的程度面试考到这道题你就稳了。