对称二叉树判断详解：递归与迭代解法全解析

几乎每个准备算法面试的人都会撞上这道题，LeetCode上的编号是101，剑指Offer里也有它，很多大厂笔试和面试环节都直接拿它当热身题。题目本身描述得很简单——给定一棵二叉树，检查它是否是镜像对称的，也就是绕着根节点看左右两边是否互为镜像。但就是这么一道“简单题”，我在实际面试候选人和带新人刷题的时候发现，真正一次写对的人非常少。很多人在理解“对称”这两个字上就掉坑了，递归函数写得不对，迭代解法更是没思路。这篇文章我就把判断对称二叉树这件事掰开揉碎讲清楚，包括递归和迭代两种解法的完整思路、代码实现、容易踩的坑，以及相关的变体题目和排查经验。

1. 先把“对称二叉树”的定义彻底想明白

1.1 初学时段最常见的一个误区

我见过不少同学一看到这道题，第一反应是判断左子树和右子树是否各自对称。他们会写出类似isSymmetric(root.left) && isSymmetric(root.right)的代码，跑几个对称的例子发现没问题，但一旦遇到非对称的树立刻翻车。问题出在哪？因为一棵树整体对称，完全不要求它的左子树单独对称，也不要求右子树单独对称。举个例子，一棵左子树长成“之”字形、右子树正好是它的镜像的树，整体是对称的，但左子树本身可能完全不对称。这个直觉上的误会是这道题最大的拦路虎，所以做题第一步不是急着写代码，而是把“镜像对称”这个概念抠清楚。

1.2 镜像关系的递归定义

对称二叉树的准确定义是：根节点的左子树和右子树互为镜像。什么叫“互为镜像”？不是两棵树长得一样，而是左子树沿着某个轴翻转之后能和右子树重合。用递归的语言描述更严谨一些：两棵二叉树t1和t2互为镜像，需要同时满足三个条件：

• t1和t2的根节点值相等；
• t1的左子树与t2的右子树互为镜像；
• t1的右子树与t2的左子树互为镜像。

看到这个定义就明白了，这是一个天然适合递归的问题。它不需要你比较同一棵树的两边，而是需要你同步比较两颗不同子树上的对称位置节点。这个“同步”是关键词：先比左子树的左孩子和右子树的右孩子，再比左子树的右孩子和右子树的左孩子，每一层都要交叉着匹配，而不是平行着比较。

用一棵具体的树说话。假设根节点是1，左孩子是2，右孩子也是2；左孩子的左孩子是3，右孩子的左孩子是3，那么这棵树是否对称？答案是false，因为左子树的左孩子3应该和右子树的右孩子去比，但右子树的右孩子是空的，空和非空不匹配。但如果左孩子的右孩子是3，右孩子的左孩子是3，左孩子的左孩子是4，右孩子的右孩子是4，也就是形如[1,2,2,4,3,3,4]的层序序列，这才是一棵真正的对称树。很多人凭视觉直观觉得“第一层相等、第二层相等、第三层相等”就够了，其实层序遍历逐层对称加上每一层内部的有序性，才构成完整的镜像条件。

2. 递归解法：用函数签名表达“镜像”关系

2.1 为什么需要辅助函数

这道题在LeetCode上只给你一个函数isSymmetric(root)，如果你试图在这个函数内部递归调用它自己，你会发现很难写。原因在于，isSymmetric(root)的入参是一棵子树的根节点，你要判断的是这棵子树根节点的左孩子和右孩子是否互为镜像，这天然就是“两棵树是否互为镜像”的比较逻辑。所以一个更干净的做法是抽出一个辅助函数isMirror(t1, t2)，专门用来判断两棵树是否互为镜像，然后把根节点的左右孩子传进去。

这个解法的核心其实就是一个函数签名的事。isMirror(t1, t2)接收两个节点，比较它们的值，然后递归比较t1.left与t2.right，以及t1.right与t2.left。因为“镜像”本质上是交叉比较，所以每一次递归都隐含着一次“翻转”的视角，这是理解整个代码的关键。

2.2 递归代码与逐步走读

先给出Python实现，这个版本最直观，后面我会再给出C++版本对比：

def isSymmetric(root): if not root: return True return isMirror(root.left, root.right) def isMirror(t1, t2): if t1 is None and t2 is None: return True if t1 is None or t2 is None: return False if t1.val != t2.val: return False return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

有几点需要特别说明。第一，空指针的判断顺序不能乱，先判断“两者都空”返回True，再判断“其中一方为空”返回False，这个顺序能保证代码安全，不会在下一步访问空指针的属性。第二，值比较放在结构判断之后，因为如果结构已经不对称了，就没有必要再取val，否则可能引发空指针异常。第三，递归的终止条件除了空节点之外，还要在值不相等时立刻剪枝返回False，这样能避免无意义的深层递归。

用一棵非对称树[1,2,2,3,null,null,3]（节点按层序编号）来模拟执行。首先isMirror(2, 2)，两个节点值相等，继续递归：isMirror(2的左孩子3, 2的右孩子null)，这里第一个条件中左节点非空、右节点为空，走t1 is None or t2 is None分支返回False。因为最后一行是and连接，只要第一个递归调用返回False，第二个递归调用根本不会执行，函数提前结束。这就是短路求值在实际算法里的意义，它让不匹配的子树能快速失败。

2.3 复杂度分析与面试追问

递归解法的时间复杂度是O(n)，因为最坏情况下需要遍历二叉树上的所有节点，其中n是节点总数。空间复杂度取决于递归深度，在最坏情况下，一棵严重偏斜的树会让递归栈深度达到O(n)，而平均情况下二叉树的高度是O(log n)，所以空间复杂度是O(h)，其中h是树高。

面试官问到递归解法之后，大概率会追问一个问题：如果这棵树特别深，递归会不会出问题？这个问题的答案和你使用的编程语言以及递归深度限制有关。以Python为例，默认的递归深度限制通常在1000层左右，如果树的高度超过这个值，就会抛出RecursionError。你在本地刷题时可能很少遇到这么深的树，但面试官问的不是“能不能跑”，而是“你有没有意识到递归栈的隐患”。这时候你如果能主动给出迭代解法的思路，会是一个很加分的表现。

3. 迭代解法：用队列同步比对，绕开递归栈

3.1 队列比对的思路来源

迭代解法最常见的做法是用队列。这个思路可以从层次遍历迁移过来：层次遍历用队列按层取出节点，而对称判断则需要在每次出队时同时取出两个节点，这两个节点就是一对应该在镜像位置上相等的节点。队列里初始放入根节点的左右孩子，之后每次从队首弹出两个节点，进行比较，再把它们各自的孩子按交叉顺序入队。

关键点在于“交叉顺序”这四个字。比较完一对节点后，需要把第一个节点的左孩子和第二个节点的右孩子成对入队，再把第一个节点的右孩子和第二个节点的左孩子成对入队。这个顺序和递归中isMirror(t1.left, t2.right)的交叉逻辑完全一致，只是把递归调用栈换成了显式队列。用生活化的类比来说，递归是“程序帮你记账”，每次递归调用都压栈保存中间状态；迭代则是“你自己记账”，在队列里显式维护下一轮要比较的所有节点对。

3.2 Python队列实现与细节处理

from collections import deque def isSymmetric(root): if not root: return True queue = deque() queue.append((root.left, root.right)) while queue: left, right = queue.popleft() if left is None and right is None: continue if left is None or right is None: return False if left.val != right.val: return False queue.append((left.left, right.right)) queue.append((left.right, right.left)) return True

这段代码有几个细节值得展开。第一，为什么遇到“两者都空”时是continue而不是直接返回True？因为队列里可能还有其他节点对等待处理，你只确认了当前这一对是匹配的，不代表整棵树已经检查完。第二，入队的顺序决定了比较的顺序，如果你不小心把(left.left, right.left)放进队列，那比较的就是同一侧的两个节点，结果必然错误。第三，用元组成对入队是一种比较清爽的写法，也可以用两个队列分别存节点，但那样代码会啰嗦不少。从可读性角度，我更推荐元组或小数组的方式。

我再用一个具体例子验证迭代过程。考虑对称树[1,2,2,3,4,4,3]。初始化队列[(2,2)]。第一轮弹出(2,2)，值相等，入队(3,3)和(4,4)。第二轮弹出(3,3)，值相等，它们的左右孩子都是空，入(null, null)和(null, null)。第三轮弹出(4,4)，同理。之后连续弹出四对空节点对，全部continue，队列清空，返回True。可以看到，迭代过程中节点对总是“镜像位置上”的一对，完全复刻了递归的交叉比较逻辑。

3.3 C++版本与递归版本对比

C++实现同样直接，这里用queue来存储节点对：

bool isSymmetric(TreeNode* root) { if (!root) return true; queue<pair<TreeNode*, TreeNode*>> q; q.push({root->left, root->right}); while (!q.empty()) { auto [left, right] = q.front(); q.pop(); if (!left && !right) continue; if (!left || !right || left->val != right->val) return false; q.push({left->left, right->right}); q.push({left->right, right->left}); } return true; }

对比两个版本的递归与迭代解法，可以列个表看各自特点：

迭代解法在最坏情况下的空间占用确实可能比递归大，因为队列里可能同时存在同一层的很多节点对。但它的优势也很明显：不受递归深度限制，逻辑可以一步步断点调试。我在实际面试中见过不少候选人递归写得飞快，但被追问“如果树有十万层怎么办”时卡壳，这时候迭代解法就是救场的钥匙。

4. 实操环节：从边界条件到测试用例设计

4.1 必须考虑的边界条件

写任何二叉树题，边界条件都是一个完整的得分点。判断对称二叉树这道题，我开始敲代码之前会先在脑子里过一遍这些场景：

• 空树：root为None，直接返回True。这一点面试时很容易被忽略，空树没有左右孩子，它当然是对称的。
• 只有一个根节点：返回True。单个节点没有子树可比较，天然对称。
• 左右孩子存在但值不相等：返回False。这是最简单的非对称场景。
• 某个子树缺失：比如左子树存在、右子树为空，返回False。这是结构上的不对称。
• 结构对称但值不对称：比如[1,2,2,3,4,4,5]，最后一个节点的值应该是3，却写成了5，判断时在第三层的某一对节点上就会触发值比较失败。

关于边界条件的细节，root为None时递归版本里要先判断，否则直接访问root.left就是空指针异常。迭代版本同样要先处理空树。这两个判断是所有解法共通的起手式，别把简单题做漏了。

4.2 构造一套可复用的测试用例

我习惯在本地建一个公共测试集，因为这个题本身函数签名简单，适合直接验证。我常用这样几个用例：

用例1: [] -> True 用例2: [1] -> True 用例3: [1,2,2,3,4,4,3] -> True 用例4: [1,2,2,null,3,null,3] -> False 用例5: [1,2,2,3,null,null,3] -> True 用例6: [1,2,2,3,4,null,null,null,null,3] -> False

第三用例是教科书级的对称树，层序从左到右读过去，每一层都是回文结构，同时还要满足交叉位置的节点存在性一致。第五用例是容易看走眼的一个：左子树的右孩子是3，右子树的左孩子也是3，整棵树依然是对称的，这里“3”出现在不同的相对位置，但因为是镜像关系，所以成立。我在带新人时经常用这个用例来检验对方是否真正理解交叉比较的逻辑，很多人在纸上画半天，最后恍然大悟——原来不是层序回文那么浅层的事情。

4.3 本地调试时的一个实用技巧

刚才说到测试用例，顺便分享一个排查技巧：当你看不出某棵树为什么不对称时，自己把树的每一层按照从左到右打印出来，再手动检查每一层是否回文，这通常能快速定位不对称发生的位置。但要注意，层序回文只是必要条件，不是充分条件。比如[1,2,2,#,3,#,3]层序是[1,2,2,#,3,#,3]，第二层2,2回文，第三层#,3,#,3不是回文，显然不对称。但也有层序回文却不对称的情况吗？有，比如结构上层序回文、但某个节点的左右孩子存在性不对称，导致它的层序遍历带空占位后不仅不守恒，反而暴露出问题。所以更好的调试方式是把空节点也用占位符打印出来，检查整层的占位序列是否关于中点对称，并且每一对对称位置上的节点父结构也满足交叉关系。这个方法在调试时很管用，尤其是在使用层序遍历验证对称性的代码里。

5. 从对称题延伸出去：高频变体与周边知识点

5.1 判断两棵树是否互为镜像

对称二叉树判定的核心子问题，其实就是“判断两棵二叉树是否互为镜像”。我在面试中经常把这道题当引子，然后追问候选人能不能把isMirror这个辅助函数单独拿出来作为一个新题写一遍。比如题目改成“给定两颗二叉树，判断它们是否互为镜像”，入参就是两个根节点，直接复用isMirror(t1, t2)。这个变体看起来简单，但它考察的是对递归定义的迁移能力。你如果只是背了对称二叉树的解法，没有理解镜像的真义，遇到这个变体可能会重新陷入“先序遍历相同”“中序遍历相同”之类的误区，而那些方法都会踩到结构重合但对称位置不匹配的坑。所以，真正掌握这道题，不是背代码，而是理解“递归交叉比较”这个底层模式。

5.2 翻转二叉树与对称性的关联

又想起另一道题——翻转二叉树（LeetCode 226），也有人叫它“反转二叉树”。如果一棵二叉树的左右孩子全部交换，得到的是一棵镜像树。那么一个有意思的推论是：一棵树是对称二叉树，当且仅当它翻转之后和自身相等。这个命题等价性可以帮助你从另一个角度理解题目，甚至在某些变体题里派上用场。实际操作中，如果你已经写好了翻转二叉树的函数，再写一个判断两棵树是否相等的函数，把两者拼起来也能解决对称判断，只是多了一次遍历和一次比较，时间上还是O(n)，但常数因子更大，不推荐面试时这么写。不过在心里记住这层关系，确实能加深对树结构操作的理解。

5.3 对称性的实际应用场景

可能有人会问，这种纯算法题除了面试，真的会出现在工程里吗？举几个我在工作中碰到过的场景。第一个是前端树组件的校验，一些UI组件的树形数据如果要求对称布局，后端返回的数据结构需要先做合法性校验；第二个是语法分析里的抽象语法树，某些编译器优化阶段会检查AST节点是否满足某种镜像等价关系，比如交换律表达式的模式匹配；第三个是图像处理里的镜像检测，虽然图像不是二叉树，但类似的分治递归思路常常迁移到图像金字塔的比较中。这些场景的共同点是：你需要比较一棵树在某种几何操作下是否保持不变性，而“对称”只是最简单的一种不变性。

写在最后的个人体会

做了这么多年算法教学和面试评审，我最大的体会是：一道题的价值不在于它本身有多难，而在于你能不能从中提炼出通用的解题范式。对称二叉树这道题，本质上考察的是你能否把“两个节点的关系模式”递归地定义清楚，然后用递归或队列把它实现出来。这种“定义清楚关系，再选择实现手段”的思路，放在很多树上题目里都适用，比如判断两棵树是否相同、判断子树、求树的最大深度，全都是同一条思路线。

还有一点想提醒大家：写这种题时不要在代码结构上过度炫技，把递归函数命名清楚、把空判断顺序摆正、把交叉比较写对，就已经拿满了分数。我见过很多候选人写一长串花哨的写法，最后却因为一个and写成了or直接错掉。简单、直接、可验证，永远是算法代码的第一追求。