LeetCode 101 对称二叉树 C语言递归与迭代解法详解

作为算法学习者遇到二叉树相关的题目是绕不开的门槛而LeetCode 101这个对称二叉树问题几乎是每位刷题人必过的关卡。别小看这道题它考察的不仅是遍历框架更是对递归出口设计、迭代遍历顺序以及空节点处理的综合理解。很多朋友在做这道题时递归版本写起来倒是顺手一到迭代就卡壳或者写出来了却搞不懂为什么要用两个队列、为什么入队顺序有讲究。这篇文章我会用C语言完整实现两种解法把每一步的思路逻辑、边界条件、甚至调试时容易踩的坑都展开说说配合我对图解思路的理解——没有画图工具我用文字把树的形态和遍历过程拆解清楚保证你看完之后不仅会写代码还能给同桌讲明白。这道题适合谁看刚刷完二叉树遍历、对递归有基础概念的同学以及想掌握迭代写法以应对面试手写场景的求职者。看完后你不仅能AC这一题还能迁移到许多比较两棵树的同类问题中。话不多说直接进主题。1. 对题目的第一眼拆解什么是对称二叉树1.1 从一棵树的镜像说起先看题目描述给定一个二叉树的根节点检查它是否轴对称。所谓轴对称可以理解为这棵树沿着根节点的垂直中线对折左右两侧完全重合。更严谨一点根节点的左子树和右子树互为镜像而镜像不仅要求节点值相等还要求左子树的左孩子和右子树的右孩子对应相等左子树的右孩子和右子树的左孩子对应相等。这里最容易出现的理解偏差是新手容易只看左右子树各自的结构是否相同比如判断左子树和右子树是否是完全一样的两棵树。这是严重错误的。对称不是相同对称是镜像。我们用一个简单例子辅助理解。假设根节点值为1左孩子为2右孩子也是2这是最简单的对称继续往下如果左孩子的左孩子是3左孩子的右孩子是4那么对应右孩子的左孩子必须是4右孩子的右孩子必须是3。也就是说从根节点出发比较的是左子树的左分支与右子树的右分支同时左子树的右分支与右子树的左分支。1.2 判断的基准条件无论递归还是迭代核心都是要比较两个节点是否满足镜像关系。假如需要比较的两个节点分别是p和q那么满足对称的条件可以拆成三条缺一不可。第一条如果p和q都为空那它们是对称的毕竟两边都没有内容第二条如果p和q中只有一个为空另一个非空那么结构不对称直接返回假第三条如果p和q都不为空那么首先要求p的值等于q的值然后递归判断p的左孩子和q的右孩子是否对称以及p的右孩子和q的左孩子是否对称。这里要注意递归判断的对象是两对节点而不是单棵树上的递归。用C语言写递归函数时明确返回类型是布尔值或者整数都行。LeetCode的C语言环境里习惯上用整数0和1表示真假。我常在代码里写一个辅助函数isMirror(struct TreeNode* left, struct TreeNode* right)主函数直接调用isMirror(root-left, root-right)。如果根节点为空按题目定义空树也是对称的直接返回1。2. 递归解法两棵子树同时展开2.1 递归函数的出口设计递归解决这个问题的优雅之处在于每一次函数调用只需要处理一个层的判断。先看边界。辅助函数接收两个指针分别代表当前需要比较的两个节点。写递归第一步必须先写终止条件我下面把判断顺序写清楚这个顺序不能乱。int isMirror(struct TreeNode* t1, struct TreeNode* t2) { if (t1 NULL t2 NULL) return 1; if (t1 NULL || t2 NULL) return 0; return (t1-val t2-val) isMirror(t1-left, t2-right) isMirror(t1-right, t2-left); }注意第二个条件我的写法是t1 NULL || t2 NULL这已经隐含了其中一个为空另一个不为空的情况。因为在第一个条件已经排除了两者都为空所以到这里还能进入这个分支的一定是恰好有一个为空。这种写法比分开写更简洁也符合C语言习惯。很多初学者容易在这里写成t1-val ! t2-val就直接返回0但这忽略了空节点的可能性会导致解引用空指针这是C语言的大忌。2.2 递归压栈过程模拟为了让你彻底看懂递归过程我们拿一棵具体的树来走一遍。假设树的结构如下1 / \ 2 2 / \ / \ 3 4 4 3根节点1非空主函数调用isMirror(2, 2)。注意这里的两个2是左右子树各自的根节点。进入函数两个都不为空值相等于是递归调用isMirror(2的左孩子, 2的右孩子)也就是isMirror(3, 3)同时还要调用isMirror(2的右孩子, 2的左孩子)也就是isMirror(4, 4)。这里的关键点在于递归调用是在同一个函数内连续执行两个isMirror。由于使用了运算符从左到右求值只有前一个isMirror返回真才会执行后一个。先看isMirror(3, 3)它的两个节点都是叶子值相等而且左右孩子都为空所以两个isMirror(NULL, NULL)都返回1整体返回真。接着执行isMirror(4, 4)同理返回真。最后整体返回真这棵树对称。接着再看一棵不对称的例子1 / \ 2 2 / \ / 3 4 4根节点1调用isMirror(2, 2)值相等。先递归判断isMirror(3, 4)这两个节点值不同直接返回0。由于短路后面的isMirror(4, 4)不会执行整个函数返回0。这里可以看到我们并不需要完整遍历整棵树一旦某一层发现不对称立刻逐层返回0效率上比迭代有时候更早停。2.3 递归解法的性能分析时间复杂度方面每个节点最多被访问一次所以为O(n)这里的n是树中节点总数。空间复杂度主要消耗在递归调用栈上。最理想的情况下树是完全对称的平衡二叉树递归深度为树的高度即O(log n)。最坏情况是树极度倾斜比如每个节点只有一个孩子并且一路延伸递归深度会达到O(n)。对于对称树的判断理论上如果树本身不对称递归可能提前终止所以实际运行时间往往低于节点的全量访问但最坏复杂度仍然是O(n)。这里要提醒一下C语言的函数调用栈是有限的如果一棵树特别深比如几万层递归可能会导致栈溢出。在LeetCode的测试数据里通常不会出现但如果在本地做极端压力测试时需要注意。这也是下面为什么要学习迭代解法的原因之一。3. 迭代解法用队列模拟分层镜像比较3.1 为什么选择队列而不是栈递归本质上是借助系统调用栈完成回溯迭代则需要我们自己管理一个数据结构。判断对称树最直观的迭代思路是把每一层需要比较的两个节点成对放入容器每次取出两个节点进行比较。这里既可以用栈也可以用队列。我优先推荐队列原因是队列的处理顺序天然符合从根向下、逐层展开的感觉而且与层序遍历的框架一脉相承。当然栈也可以做到只要保证每次弹出的两个节点是配对的具体顺序不影响对称判断的正确性。如果选择队列我们需要一个能存储节点指针的队列。C语言标准库没有内置队列所以要么自己用数组模拟要么使用链表实现。在LeetCode刷题环境中最实用的是用一个动态数组模拟环形队列或者简单用数组头尾下标。考虑到题目中节点数量未知为了安全我通常直接用一个足够大的静态数组或者调用malloc动态分配。这里为了演示清晰我用动态数组的形式同时把队列操作封装好。3.2 入队顺序的巧妙设计迭代的核心思路是最开始将根节点的左右孩子放入队列这两个节点是第一次需要比较的镜像对。之后每次从队列中取出两个节点记为leftNode和rightNode比较它们的值。如果相等则按照leftNode的左孩子 与 rightNode的右孩子配对入队再按照leftNode的右孩子 与 rightNode的左孩子配对入队。每次入队都是成对入队这保证了后续出队时拿到的两个节点一定是需要比较的镜像节点。这里容易搞错的细节是当某个节点为空时要不要入队答案是空节点也要入队。因为我们不仅要比较值还要比较结构。如果节点为空直接跳过不处理会丢失这一侧有节点、另一侧没有节点的信息导致误判。举个例子如果左子树有左孩子而右子树的右孩子为空那么这一对节点应该被比较发现一个非空一个为空结果返回0。如果空节点不入队那么在这层比较时我们根本不知道这里存在过不对称的结构。正确的处理方式是取出leftNode和rightNode后首先检查它们是否都为空。如果都为空说明这一对节点不存在且没有孩子需要继续比较直接跳过本轮继续取下一对。如果只有一个为空说明结构不对称直接返回0。如果两个都不为空检查值是否相等。相等时把它们的四个相关孩子按镜像配对规则入队这里注意四个孩子中可能某几个为空但依然要入队因为下一轮比较时需要用空和非空来判定结构。3.3 C语言队列实现细节我用一个结构体封装动态数组队列。提供三个基础操作初始化、入队、出队。为了简单我直接使用struct TreeNode*数组。下面的代码是我在LeetCode上验证过的写法你可以在本地测试。/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSymmetric(struct TreeNode* root) { if (root NULL) return true; struct TreeNode** queue (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 2000); int head 0, tail 0; // 初始时根节点的左右孩子入队 queue[tail] root-left; queue[tail] root-right; while (head tail) { struct TreeNode* t1 queue[head]; struct TreeNode* t2 queue[head]; if (t1 NULL t2 NULL) continue; if (t1 NULL || t2 NULL) { free(queue); return false; } if (t1-val ! t2-val) { free(queue); return false; } // 注意入队顺序左的左 vs 右的右左的右 vs 右的左 queue[tail] t1-left; queue[tail] t2-right; queue[tail] t1-right; queue[tail] t2-left; } free(queue); return true; }上面代码中我使用了固定大小的数组。题目给的数据范围一般不会让队列超过这个容量但在更严格的工程环境中建议动态扩容。LeetCode上这种写法通过没问题。如果你担心容量不够可以改为每次入队时检查tail是否超过容量超出则用realloc扩容。这里为了简洁我先用固定大小后面在常见问题里再讲扩容方式。注意每轮循环要出队两个节点。如果队列中节点数量不是偶数说明之前的入队操作配错了对。但在我们严格的成对入队逻辑下只要初始为两个后续每次出队两个、入队四个队列长度始终是偶数所以不会发生这种情况。3.4 迭代执行流程模拟继续用前面那棵对称树举例。初始队列[2, 2]。出队两个2值相等分别把左2的左孩子(3)和右2的右孩子(3)入队再把左2的右孩子(4)和右2的左孩子(4)入队。此时队列变成 [3, 3, 4, 4]。下一轮出队3和3都为叶子左右孩子全部为空继续。出队4和4同理。队列为空后返回真。再模拟不对称树初始入队 [2, 2]。出队后值相等将队列变成 [3, 4, 4, null]。注意最后一个null是右子树2的左孩子位置缺失。下一轮出队3和4值不相等立即返回假。这里我们看到如果当时没有把null入队那么这个位置可能被误认为没有节点而实际上不对称性在第一层就已经暴露了。所以null入队是迭代解法最关键的细节之一。3.5 迭代解法的复杂度时间复杂度和递归一样也是O(n)。空间复杂度是O(n)因为队列中最多会存储某一层的所有节点最坏情况下完全二叉树最后一层大约有n/2个节点。但这里我们存储的是成对节点所以空间依然O(n)。迭代的一个好处是不用担心递归深度导致的栈溢出这对处理深度很大的树更友好。不过代价是需要手动管理队列代码相对繁琐。面试时如果被要求手写通常默认写递归版本更快但如果面试官追问非递归写法队列法是最自然的回答。4. 递归与迭代的对比各自优势与适用场景4.1 代码可读性与面试选择递归代码极其简洁5行完成核心逻辑非常适合用来表达镜像比较这个语义。面试时提到对称二叉树几乎所有面试官都期待你先给出递归思路因为它最容易解释。但面试官也喜欢追问一句如果树很深递归会不会有问题请写一个迭代版本。所以两种写法都要掌握但心里要有优先级先说递归再补充迭代。迭代版本虽然代码长一些但它的思路其实更贴近人类逐层观察的方式。我曾经在面试时先写递归然后面试官问我能否用非递归实现我便改用队列并把空节点入队这个关键点主动讲出来面试官立刻点头。实际上很多候选人写着写着就把空节点弄丢了导致逻辑错误。如果你能把这一点放在前面讲清楚印象分会提高不少。4.2 性能实测对比我自己在LeetCode上提交过两个版本。递归版本的运行时间通常介于0ms到4ms之间迭代版本也差不多。空间上两者在不同形态的树上表现不一样。随机平衡树两者差不多极深链状树迭代稳过递归可能爆栈。所以在生产环境中如果需要处理不可控深度的二叉树我优先选择迭代方案。但在刷题阶段为了最短时间内AC递归是首选。4.3 一个容易踩的坑C语言中bool的包含LeetCode的C环境里直接使用bool类型是可以的因为编译器已经包含了相关头文件。但在本地IDE中如果只写了标准输入输出没有包含stdbool.h那么bool、true、false都会报错。我记得自己第一次在本地调试时就是忘了加这个头文件结果编译报错半天。你如果习惯用int和0/1来写也可以避免这个烦恼。不过我建议统一用bool语义清晰记得加头文件就好。5. 图解思路用文字还原对称树的比较过程5.1 分层视角的图形化描述对称二叉树的判断过程可以看成是对每一层节点从两侧向中间挤压合并。想象这棵树被根节点分成左右两半我们用两个指针分别从左右两侧出发沿着镜像路径同步移动。第一层比较左右根第二层比较左之左与右之右、左之右与右之左第三层继续递归。递归调用的树形展开本身就像一棵倒置的“比较树”每次分解成两个子问题。如果硬要画图我们可以把每次比较的节点对用括号表示例如第1层: (2, 2) 第2层: (3, 3) (4, 4) 第3层: ((3的左,3的右), ...) 分解迭代版本的层序过程则类似于宽度优先扫描每一层都维护一个待比较节点对的队列。队列里的元素永远是两个一组这就是“对称比较波纹”在数据结构上的体现。理解了这一层再去看代码中的四次入队就不会打架了。5.2 边界情况图形化空节点位置的标记我们经常遇到的一种情况是左子树比右子树多一层但多出来的节点恰好都在内侧。比如1 / \ 2 2 / \ 3 3这棵树是对称的吗答案是肯定的。左子树2的左孩子是3右子树2的右孩子是3对应镜像关系成立。如果你用递归会比较isMirror(3, 3)它们都是叶子返回真。用迭代时初始队列为 [2, 2]出队后入队 [3, null, null, 3]。注意这里入队的顺序第一个3是左2的左孩子第二个null是右2的右孩子等等我们需要重新整理一下。按照规则第一次出队t1左2t2右2入队顺序为t1-left (3) 与 t2-right (3) 配对t1-right (null) 与 t2-left (null) 配对所以队列实际为[3, 3, null, null]。下一轮出队3和3值相等两个节点都是叶子它们的左右孩子都是null于是入队 [null, null, null, null, null, null, null, null]仔细想想3的左右孩子都是空t2-right也空所以四个配对的入队其实是 [null, null, null, null, null, null, null, null]不是的每次出队两个3每个3要分两次入队第一次把t1-left(null)和t2-right(null)入队第二次把t1-right(null)和t2-left(null)入队。也就是四个null。接着再出队null和nullcontinue。所以整体返回真。这里可以看出来空节点的传递会让队列多出很多空位但不要紧它们会被成对消费掉。再看看不对称的情况1 / \ 2 2 / \ 3 4初始队列[2,2]出队后入队 [3, null, null, 4]。下一轮出队3和null发现一个非空一个空立即返回假。很好结构不对称被识别出来了。5.3 从不完全对称的变体中学到的有一种变体是根节点的左右孩子值相同但下面的结构出现了“外侧缺失”比如1 / \ 2 2 / \ 3 3这个我们刚判断过是对称的。那如果把上面的树改成左子树多了一个4挂在3右边右子树却在对应位置没有节点如下1 / \ 2 2 / \ 3 3 \ 4这里左子树整体是 2-3-4右链右子树整体是 2-3右链。对称吗显然不对称因为右侧缺少了对应4的位置。递归过程中比较isMirror(3,3)时两者值相等但3的左孩子和右孩子左3的左孩子为null右3的右孩子为null配对成功左3的右孩子为4右3的左孩子为null一个非空一个空所以返回假。迭代版本会走到队列中的一对 (4, null)然后返回假。通过这两个例子可以看到“空节点入队”和“递归时比较孩子对”是多么重要。6. 常见问题与排查技巧实录6.1 递归写法为什么返回了错误结果有同学写递归时喜欢把主函数和辅助函数分开这没问题但容易在主函数里写错判断条件。比如在主函数里先比较左右孩子值然后递归调用自身而不是调用辅助函数。曾有朋友写出这样的代码bool isSymmetric(struct TreeNode* root) { if (root NULL) return true; if (root-left NULL root-right NULL) return true; if (root-left NULL || root-right NULL) return false; return root-left-val root-right-val isSymmetric(root-left) isSymmetric(root-right); }这个代码在简单的对称树上可能通过但遇到我之前举的复杂镜面对称树就会出错。原因在于isSymmetric(root-left)只检查了左子树本身是否对称而不是和右子树进行镜像比较。对称树要求左子树与右子树互为镜像而不是各自内部对称。内部对称的树比如节点2的左孩子是3右孩子是4右子树的节点2左孩子是4右孩子是3整体才是对称的。如果改为各自内部对称整个判断标准就变了。所以一定要用双参数的辅助函数。6.2 迭代写法中忘记处理空节点这是迭代最常见的bug。很多人判断完t1和t2的值后直接检查左右孩子是否存在存在才入队不存在就不管。这样做的后果是当一侧的节点深入到某层为空、另一侧对应位置是非空时无法被检测出来。举一个具体例子1 / \ 2 2 / \ 3 3 \ 4左树有4右树没有。迭代时第一次出队2和2入队左2的左(3)和右2的右(3)入队左2的右(null)和右2的左(null)此时队列为[3,3,null,null]。如果跳过空节点队列就变成[3,3]下一轮比较3和3发现相等随后入队的只有左3右孩子4和右3左孩子null如果继续跳过null队列变成[4]下一次取出一个节点4程序可能出错因为约定每次取两个。即使硬取也可能导致队列长度不匹配。所以不能跳过空节点而是要在比较阶段明确处理。6.3 本地调试时如何构造测试用例我建议你写一个简单的建树函数利用数组表示层序序列空节点用特殊值标记比如INT_MIN。因为C语言中直接手写节点结构太繁琐层序数组转树是最快的。下面给一个简单实现示例方便你在本地验证上面两个版本的代码。#include stdio.h #include stdlib.h #include stdbool.h #include limits.h struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; struct TreeNode* createNode(int val) { struct TreeNode* node (struct TreeNode*)malloc(sizeof(struct TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } struct TreeNode* buildTree(int* arr, int size) { if (size 0 || arr[0] INT_MIN) return NULL; struct TreeNode** nodes (struct TreeNode**)malloc(sizeof(struct TreeNode*) * size); for (int i 0; i size; i) { if (arr[i] INT_MIN) nodes[i] NULL; else nodes[i] createNode(arr[i]); } for (int i 0; i size; i) { if (nodes[i] NULL) continue; int leftIdx 2 * i 1; int rightIdx 2 * i 2; if (leftIdx size) nodes[i]-left nodes[leftIdx]; if (rightIdx size) nodes[i]-right nodes[rightIdx]; } struct TreeNode* root nodes[0]; free(nodes); return root; }本地测试时把int arr[] {1, 2, 2, 3, 4, 4, 3};传进去调用isSymmetric(root)打印结果。这里要注意如果数组用INT_MIN表示空节点那么节点值不能出现INT_MIN实际题目中的节点值范围在[-100, 100]所以没问题。构建树时如果某节点为空其孩子即使有值也无法正确建立所以层序数组需要把空节点孩子的空位置也补上INT_MIN这里示例代码已经考虑了这一点但前提是数组符合完全二叉树的层序填充方式。LeetCode测试用例通常用这种格式存储。6.4 队列容量扩容技巧如果你不想固定分配大数组可以封装一个动态队列。每次入队前检查tail是否等于容量相等则执行容量翻倍并拷贝。这里要注意使用realloc后原来的指针会自动被释放或移动所以只用维护新的指针即可。head和tail是相对数组起始位置的偏移量realloc不会改变两者的相对关系所以可以直接更新数组指针后继续使用。由于我们不能改LeetCode函数的签名所以在函数内部使用静态局部数组或者动态分配都是允许的。固定2000在题目限制下足够但如果节点数可到10000最好改成动态扩容。这里我提供一个小技巧既然队列长度最多为节点数的两倍你可以先遍历树计算节点总数如果你有现成的计数函数然后精确分配。遍历一次会增加一点开销但能保证不浪费内存。6.5 测试数据的陷阱LeetCode的判定中节点值可能出现负数所以不要用-1作为特殊值。调试时我用INT_MIN作为占位符。另外要注意空树返回真单节点返回真这两个边界一定要在本地先测。还有一个极端情况根节点只有左孩子没有右孩子一定返回假因为结构不对称但如果你在代码里只比较值空指针解引用会导致程序崩溃。所以先判断空指针再比较值这个顺序必须严格遵守。7. 扩展思考从对称二叉树到更一般的镜像问题7.1 同一套思路迁移到其他题目对称二叉树的递归写法其实可以抽象成比较两棵树是否互为镜像的原型。很多其他题目都基于这个框架。举例来说判断两棵树是否相同只需要把递归比较条件改成左比左、右比右而不是左比右、右比左。判断一棵树是否是另一棵树的子树也需要在遍历中不断比较两棵子树是否相同。再比如反转二叉树其实就是把每个节点的左右孩子交换而对称树可以理解为把左子树反转后与右子树相同。所以吃透这道题的递归解法后面的许多树题会变得异常简单。迭代版本同样可以模板化。用一个队列存需要比较的节点对入队顺序决定比较关系。这个模式在检查两棵树是否结构相同的迭代写法中也能复用只要把配对入队的顺序改成对应位置即可。7.2 进一步优化是否可以用后序遍历或Morris遍历我见过有人讨论是否可以用后序遍历来判断对称。思路是分别对左子树和右子树进行特定的遍历序列然后比较序列是否相等。若对左子树进行根右左遍历对右子树进行根左右遍历如果两棵子树在该自定义遍历下序列一致则这棵树对称。这种办法从理论上可行但要额外申请存储且需要定义清楚空节点的表示。不过它揭示了一个角度对称本质上是两种遍历序列的反向匹配。Morris遍历能在O(1)空间遍历二叉树对称判断如果需要同时比较两个序列则需要两个Morris遍历的协同推进实现难度较高面试极少要求作为扩展了解即可。我自己在练习时通常先用递归快速解决问题然后强迫自己再写出迭代版本。这个习惯让我在手写队列时越来越熟练也深刻理解了为什么递归写法在代码清晰度上无可替代。对称二叉树这道题像是二叉树遍历框架的“集大成者”能把递归、迭代、边界处理都串起来。7.3 最后再分享一个小技巧调试二叉树的递归函数时我们往往很难直观看到调用过程。我建议在本地加一个全局深度计数变量在递归函数入口打印当前比较的两个节点值出口前缩进。比如int depth 0; int isMirrorDebug(struct TreeNode* t1, struct TreeNode* t2) { for (int i 0; i depth; i) printf( ); printf(compare %d %d\n, t1 ? t1-val : -1, t2 ? t2-val : -1); depth; // 原有逻辑... depth--; }这样你能直观看到递归的路线。对于理解镜像配对效果比看代码要好得多。如果你在迭代版本中出了问题也可以打印每次出队和入队的节点值看配对是否正确。我记得有一次在本地调试时发现入队顺序写错了把相邻配对写成了左右错位打印队列后立刻发现第一个t1的左孩子和t2的左孩子被放在了一起赶紧修正。打印调试法虽然原始但排查树形结构问题真的非常有效。通过这道题希望你对“镜像”这个概念有更深的理解也掌握递归和迭代两种思路在树结构中的应用。接下来如果再遇到类似的“比较两棵树”的题目你就能举一反三轻松应对了。