对称二叉树判定：从镜像比较到递归与迭代的完整实现

1. 题目本身在考什么——对称二叉树背后的“镜像比较”逻辑LeetCode热题100里这道对称二叉树Symmetric Tree在我还是面试新手的时候第一反应是“这不是中序遍历然后判断回文就行了”——然后就被测试用例教育了。这道题真正想考察的不是你会不会遍历一棵树而是你有没有把“树结构”理解成“可递归比较的对象”以及你能不能把一个看似整体的树拆成左右两个子树之间的镜像关系。题目描述很简洁给定一个二叉树检查它是否是镜像对称的。示例tree是[1,2,2,3,4,4,3]一眼看过去确实对称但反例[1,2,2,null,3,null,3]会让你意识到光看“值”没用关键得看结构。镜像对称的本质是根节点的左子树和右子树互为镜像。什么叫互为镜像就是左子树的左孩子对应右子树的右孩子并且这两个节点的值相等左子树的右孩子对应右子树的左孩子值也相等以此类推往下递归。用一句话概括——对称二叉树判断的不是“一棵树”而是“两棵树”之间的镜像相等关系。这个认知一旦建立不管是用递归还是迭代思路都会非常清晰。你不可能直接拿root.left和root.left比那是“相等”不是“对称”你要比的是root.left.left和root.right.rightroot.left.right和root.right.left。很多初学的朋友卡就卡在这里——不是不会写递归而是不知道递归该比较谁和谁。这道题的另一个价值在于它是一道缩影。树相关的“判断类”题目比如“相同的树”“翻转二叉树”“路径总和”核心逻辑都建立在“如何用递归或迭代方式去比较/变换树的局部”上。把对称二叉树吃透后面刷树相关题目会顺畅很多。所以这篇笔记我打算把两种主流做法完整拆开从入参、终止条件、递归函数设计到迭代的队列/栈使用全部讲透顺便把一些容易出错的边界情况一并拿出来晒晒太阳。2. 前置功底树的遍历基本功决定你能否一步写出题解对称二叉树这道题虽然看起来简单但如果你对树的遍历方式没有形成肌肉记忆直接上来写递归会有些别扭。更准确地说这道题默认要求你具备这么几个基础能力第一知道二叉树的节点定义。LeetCode的Java版本是public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }在写题解之前先把TreeNode类理解清楚val是节点值left和right是左右子节点引用构造方法支持无参、只传值、传值加左右子树三种形式。很多本地调试卡住恰恰是构造测试用例时不会用三参构造方法。第二了解递归遍历树的基本套路。不管是先序、中序还是后序核心都是“处理当前节点 递归左右子树”。对称二叉树这道题里递归的粒度不是“处理单棵树”而是“同时处理两棵树”——左子树和右子树。这在本质上要求你跳出“单根节点”的思维模式转向“双节点比较”的递归视角。这也是很多人会忽略的一层基本功树的递归不只有单树遍历双树对比同样常见。第三了解迭代遍历树时用到的辅助结构。递归翻译成迭代一般来说要么用栈要么用队列。树的广度优先遍历BFS用队列深度优先遍历DFS用栈。对称二叉树在迭代解法里本质上是在用队列或栈模拟“成对比较”的过程所以你需要对Queue接口的实现类比如LinkedList和Deque双端队列的常见方法足够熟悉。以下是三种前置能力的对照总结刷这道题前最好确认自己都掌握了基础能力涉及知识点对称二叉树中的应用节点定义TreeNode类的字段与构造方法构建测试用例理解左右子树引用递归思想返回值设计、终止条件、递推公式递归比较左子树与右子树迭代遍历队列的BFS、栈的DFS成对入队或入栈循环比较如果这些基础还不太牢我建议你先别急着看题解先去把“二叉树的前中后序遍历”用递归和迭代两种方式各写一遍写熟练了再回来做对称二叉树会轻松很多。我自己当初就是先卡在“迭代前序遍历怎么写”回来补课后才发现对称二叉树的迭代解法就是在那个基础上加了个“pair”概念。3. 递归解法最容易上手的对称判断实现3.1 递归函数的设计思路递归解法看起来篇幅很短但如果对“谁和谁比较”没想清楚很容易写出虽然能通过部分用例但整体逻辑有问题的代码。我在本地做这道题时犯过的第一个错误是试图在isSymmetric里只接收一个root参数就完成递归后来发现不行因为你需要同时拿左子树的某个节点和右子树对应的镜像节点做比较。正确的做法是拆成两层方法外层方法isSymmetric(TreeNode root)处理空树的情况然后调用内层方法进行比较。内层方法isMirror(TreeNode left, TreeNode right)判断两棵子树是否互为镜像。内层方法是核心。对比逻辑拆成三步如果两个节点都为null说明对称返回true。如果只有一个为null说明结构不对称返回false。如果两个节点值不相等返回false否则继续递归比较left.left和right.right同时比较left.right和right.left两者同时成立才返回true。这里最微妙的就是“值相等后比较的配对关系”。我第一次忽略的就是这个配对顺序写成了isMirror(left.left, right.left)结果面对不对称的树也返回true。后来画图走了一遍才意识到左子树的左孩子正对的是右子树的右孩子中间隔着一根“镜像轴”。这个配对关系是整个题解的灵魂。3.2 完整Java代码与执行流程拆解这里给出我本地自测通过的递归版本class Solution { public boolean isSymmetric(TreeNode root) { if (root null) { return true; } return isMirror(root.left, root.right); } private boolean isMirror(TreeNode left, TreeNode right) { // 两个都为空镜像对称 if (left null right null) { return true; } // 一个为空一个不为空结构不对称 if (left null || right null) { return false; } // 两个节点值不等直接false if (left.val ! right.val) { return false; } // 递归比较left的左子树 vs right的右子树left的右子树 vs right的左子树 return isMirror(left.left, right.right) isMirror(left.right, right.left); } }注意这里left null || right null这个判断非常关键它能在第二个if已经排除了“都不为空”的情况下精准捕获“一空一非空”的情况比单独写(left null right ! null) || (left ! null right null)简洁得多。我用示例树[1,2,2,3,4,4,3]手动推演一下调用过程帮你建立起“递归栈”的感觉调用isMirror(root.left, root.right)也就是isMirror(2, 2)。两个节点值都为2相等继续调用isMirror(3, 3)和isMirror(4, 4)。isMirror(3, 3)中两个节点值相等且左右子树都为null递归返回trueisMirror(4, 4)同理true。两个true做逻辑与最终返回true判定镜像对称。再看反例[1,2,2,null,3,null,3]调用isMirror(2, 2)值相等继续递归。这里二叉树的结构是根1的左子树2的右孩子为3左孩子为null右子树2的左孩子为null右孩子为3。于是比较isMirror(left.left, right.right)即isMirror(null, 3)——一个为空一个不为空直接返回false。由于这里是逻辑与短路求值整个结果直接为false。这个执行流程走一遍之后就能理解为什么每次递归都要“穿过镜像轴”去看对应的节点而不是直观地比较挨着的节点。3.3 递归的时间与空间复杂度分析时间复杂度上每个节点在递归过程中都会作为某个比较对中的一个元素被访问一次整体上每个节点约被访问一次所以是O(n)其中n是树的节点数。空间复杂度方面递归的深度与树高相关最坏情况是树退化成链状高度为n所以空间复杂度是O(n)递归栈的深度最好情况是完全平衡二叉树高度为log n空间复杂度O(log n)。有一个细节值得注意这里的“每个节点约访问一次”之所以带个“约”字是因为极端情况下比如树根的左子树很大、右子树很小递归比较会在发现不匹配时提前结束并不会真的把所有节点都访问完。但对于复杂度上界来说我们还是按最坏情况O(n)来计算。刷题时如果面试官追问“递归会栈溢出吗”你可以回答如果树高度极大比如10万层的链状树递归深度可能超出JVM默认栈大小这时候迭代解法就更合适。这个回答既能体现你对边界情况的认知也能自然地带出迭代解法的存在意义。4. 迭代解法拆掉递归栈之后题目的真实难度才浮现4.1 为什么需要迭代解法递归写法简洁易懂但有两个实际痛点。第一递归栈深度受JVM栈大小限制。如果树的高度达到几万层递归版本会出现StackOverflowError。虽然LeetCode测试用例里不太会出现这种极端数据但在真实工程中你无法保证传入的树是温和的。尤其是在处理某些“偏斜树”skewed tree时递归的脆弱性会暴露无遗。第二面试场景下面试官经常会追加一句“你再用非递归方式写一遍。”这不是刁难而是想看你对递归本质的理解——毕竟递归本身就是借助JVM的函数调用栈本质上是“系统帮你管理栈”。把你递归改成迭代你会发现它其实就是一个“手动管理栈或队列”的过程。能写出迭代版本说明你对递归栈里每一层的状态变化都心里有数。从BFS和DFS两种遍历范式出发对称二叉树的迭代有两种常见形式基于队列的BFS式成对比较最直观基于栈的DFS式成对比较本质上和队列版本一样只是取出顺序不同4.2 双端队列BFS解法成对入队成对出队用队列做对称判断的核心思路是每次从队列头部取出两个节点这两个节点应该是“互为镜像”的位置如果它们值相等就把它们的孩子按“镜像配对”的顺序继续放入队列中。具体操作如下如果根节点为空直接返回true。初始化一个队列Java里用DequeTreeNode或QueueTreeNode都可以先把root.left和root.right依次放入队列。进入while循环只要队列不为空取出两个元素a和b按放入顺序。如果a和b都为空continue继续处理下一对。如果a或b有一个为空返回false。如果a.val不等于b.val返回false。关键步骤把a.left、b.right、a.right、b.left依次放入队列。其实“a.left和b.right”是一对所以可以理解为先放a.left再放b.right接着放a.right再放b.left。这样下一次循环时取出的前两个恰好就是需要比较的一对。循环结束后返回true。对应Java代码import java.util.Deque; import java.util.LinkedList; class Solution { public boolean isSymmetric(TreeNode root) { if (root null) { return true; } DequeTreeNode deque new LinkedList(); deque.offer(root.left); deque.offer(root.right); while (!deque.isEmpty()) { TreeNode left deque.poll(); TreeNode right deque.poll(); if (left null right null) { continue; } if (left null || right null) { return false; } if (left.val ! right.val) { return false; } // 按照镜像对放入队列 deque.offer(left.left); deque.offer(right.right); deque.offer(left.right); deque.offer(right.left); } return true; } }一个小坑是不要一次性把四个节点全都offer进队列再一次性poll出两个来比较。如果这样你每次循环取出的一对很可能是“left.left和right.right”吗按入队顺序left.left, left.right, right.left, right.right来推取出的两个会是left.left和left.right这俩根本不是镜像对。我当初这里写错过排查了好久才发现是入队顺序破坏了“配对”。更稳的写法是严格按“先a.left再b.right再a.right再b.left”的顺序入队或者更直白一点每次循环只处理一对节点配对顺序一目了然。如果担心Deque的offer/poll方法不熟直接用LinkedList当作Queue来用也行QueueTreeNode queue new LinkedList();两者的区别在于QueueTreeNode接口不支持双端操作但在本题中只需要从尾部入队、从头部出队完全够用。Deque虽然功能更多反而可能让人产生“从尾部取元素”的混淆。4.3 栈DFS解法换一种数据结构逻辑不变既然队列能实现对称判断那栈呢也可以。队列是先进先出栈是后进先出。但本题的关键不在于“先处理谁”而在于“每次都从容器里取出两个互为镜像的节点做比较”。只要保证入栈时依然按镜像配对的方式入栈栈的取出顺序反而无关紧要。DFS版本示例import java.util.Deque; import java.util.ArrayDeque; class Solution { public boolean isSymmetric(TreeNode root) { if (root null) { return true; } DequeTreeNode stack new ArrayDeque(); stack.push(root.left); stack.push(root.right); while (!stack.isEmpty()) { TreeNode right stack.pop(); TreeNode left stack.pop(); if (left null right null) { continue; } if (left null || right null) { return false; } if (left.val ! right.val) { return false; } stack.push(left.left); stack.push(right.right); stack.push(left.right); stack.push(right.left); } return true; } }注意这里我用的是push和pop并且先stack.push(left.left)、再push(right.right)然后push(left.right)、push(right.left)。这样每次弹出两个时第一个弹出的其实是left.right第二个是right.left——它们确实是一对镜像位置。再往下弹得到left.left和right.right也是一对。这个版本验证过是能跑通的。但必须承认栈版本和队列版本的代码几乎没有本质差异都是“成对入容器、成对出容器、按镜像顺序放孩子”。这也说明了一件事对称二叉树的迭代解法本质上就是BFS和DFS共用的同一个模板只是容器的选择不同。面试的时候能把这句话讲清楚比背100行代码更能体现你对算法的理解程度。4.4 迭代解法的复杂度与边界情况迭代解法的时间复杂度同样是O(n)每个节点最多入队/入栈一次出队/出栈一次。空间复杂度上最坏情况是树完全平衡时队列里最多同时存在约n/2个节点最后一层所以空间复杂度也是O(n)。但如果树的形状很偏斜递归版本的空间复杂度反而可能是O(n)栈深迭代版本的空间复杂度也能到O(n)容器中同时存在节点数量可能不多这两者在上界上是一样的只是常量因子不同——迭代版本不占用JVM调用栈没有StackOverflowError风险。边界情况主要注意四点空树root null时返回true。空树可以认为是镜像对称的因为没有任何破坏对称性的节点。单节点树[1]root.left和root.right都为null递归或迭代都会直接返回true。左右子树都为空的情况根节点左右孩子都为null依然对称。值相同但结构不同的树比如[1,2,2,null,3,null,3]这就是经典反例。值相同救不了结构不对称。这四个边界情况分别对应代码里的哪个分支可以自己走一遍验证加深记忆。5. 两种实现到底怎么选——耗时、易错点与通用性对比5.1 实测耗时与代码量对比我在本地用LeetCode的示例用例、自己构造的极端用例和几棵随机生成的二叉树做了对比。从纯运行时间来看递归和迭代几乎没有肉眼可感知的差异——因为节点数量在LeetCode这个量级下通常几百到几千个节点O(n)的差距本来就不大。但如果把节点数拉到百万级递归方式的调用栈开销和函数调用开销会更明显迭代方式虽然也有装箱和容器操作的开销但相对可控。代码量方面递归明显更短核心逻辑一个方法搞定迭代需要更多的“成对维护”代码将近多出一倍。如果你是面向面试刷题优先掌握递归再把迭代作为进阶理解。如果你是在真实项目中做工具类可能更倾向于迭代因为它不用考虑递归深度问题。5.2 易错点对比递归更隐蔽迭代更直接我总结了递归和迭代各自最容易翻车的地方对比维度递归写法迭代写法核心易错点镜像配对的参数顺序写错入队/入栈顺序破坏配对出错表现反转示例树结果变成true有时返回结果随机正确或错误定位难度需要画递归树才能发现打印容器内容即可定位调试建议从第二层递归开始打印每轮循环打印take的一对值递归写法的易错点隐蔽在于代码语法完全正确逻辑看起来也对但比对参数一错就满盘皆输。比如我曾把isMirror(left.right, right.right)写成isMirror(left.right, right.left)在某个节点少的用例里居然也能通过换到大树用例才暴露。这种错很难一眼看出来得靠对“镜像轴”的心智模型才能发现。迭代写法的易错点更“物理”入队/入栈顺序一旦乱调试时打印出来的比对结果就会完全乱套。但好处是你可以非常直观地看到容器里每一层的元素定位问题很快。5.3 实际开发场景的选型建议如果是LeetCode刷题或者面试现场我的建议是面试首选递归因为代码简洁面试官看起来舒服你也容易讲清楚思路。如果面试官追问栈溢出或者让你优化再展示迭代版本。如果是工作里写一个工具方法且树的深度不可控直接用迭代。如果想练好“树”这一类题目递归必须练到条件反射迭代至少能写队列版本。顺带说一句LeetCode的Java版执行环境默认栈大小不低通常几万层递归不会爆掉但本地IDE里你如果不手动调大-Xss跑一个10万层的递归可能就StackOverflowError了。这也是为什么有些人在LeetCode上递归能跑过本地一测就挂的原因。6. 对称二叉树只是开始同类题目的举一反三6.1 与“相同的树”“翻转二叉树”的关系对称二叉树说白了就是“左子树和翻转后的右子树是否相同”。这句话信息量很大。LeetCode上另外两道经典题目——Same Tree相同的树和Invert Binary Tree翻转二叉树——与对称二叉树有极强的关联。相同的树判断两个二叉树是否完全相同递归核心是比较节点值、左子树与左子树、右子树与右子树。翻转二叉树把一棵树的所有节点的左右子树互换。对称二叉树如果用“翻转相同”的方式表达可以写成public boolean isSymmetric(TreeNode root) { if (root null) return true; TreeNode invertedLeft invertTree(root.left); return isSameTree(invertedLeft, root.right); }这当然不是最优解凭空多了一棵翻转后的树空间开销变大但它帮你建立了“定义之间的联系”。面试时如果能说出“对称 左子树翻转后与原右子树相同”通常会让面试官眼前一亮。6.2 一道题的N种变形对称二叉树不仅要求你理解递归还能延伸出不少变体题目。比较常见的有对称的二叉树剑指Offer版和LeetCode 101题几乎一样不用重新刷。给定二叉树将其调整为对称二叉树需要你对树做变换比单纯判断多一步操作。判断二叉树的子树是否对称比如求所有对称子树的个数这需要对每个节点都跑一次isSymmetric。扩展K叉树的对称判断如果每个节点有超过两个子节点镜像轴怎么定义左右镜像、还是关于中心镜像不同定义导致算法完全不同。验证回文树中序遍历结果是否为回文。这个思路虽然不对经典反例但它能帮你理解“树的序列化结果与结构信息”之间的差异。看到这些变形你就明白了对称二叉树不只是背答案背后其实是“树的镜像关系”这一个核心概念的多次表达。把这一道题吃透等于顺带预习了同类型的一批题。6.3 实战技巧用一段代码快速构造测试用例刷树题目时最烦的事情之一就是怎么快速构造一棵测试树。LeetCode上直接给的是层序序列化数组[1,2,2,3,4,4,3]但本地调试时往往需要手动new节点非常麻烦。这里分享一个我在本地用的构造方法能把层序数组转成二叉树public static TreeNode buildTreeFromLevelOrder(Integer[] arr) { if (arr null || arr.length 0) return null; TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1; while (!queue.isEmpty() i arr.length) { TreeNode node queue.poll(); if (arr[i] ! null) { node.left new TreeNode(arr[i]); queue.offer(node.left); } i; if (i arr.length arr[i] ! null) { node.right new TreeNode(arr[i]); queue.offer(node.right); } i; } return root; }然后main方法里直接写public static void main(String[] args) { Solution solution new Solution(); TreeNode tree1 buildTreeFromLevelOrder(new Integer[]{1,2,2,3,4,4,3}); TreeNode tree2 buildTreeFromLevelOrder(new Integer[]{1,2,2,null,3,null,3}); System.out.println(solution.isSymmetric(tree1)); // true System.out.println(solution.isSymmetric(tree2)); // false }用Integer[]而不是int[]的原因是层序数组里会有null标记表示空节点int[]没法表达空值。这是本地调试中很实用的小技巧尤其适合对称二叉树这种需要频繁构造“真/假”两种树的题目。我在本地测试时还喜欢写一个“暴力随机生成树”的方法结合isSymmetric跑一遍再把输出树结构打印出来用来验证算法在奇怪用例下的表现。6.4 对称性与算法之外的思考对称二叉树这道题从算法角度很简单但“对称性”本身是一个很值得品的东西。在数据结构的世界里很多高效算法的前提都是某种对称性AVL树的平衡因子就是左右子树高度差不超过1堆的完全二叉树结构天然就是“层序对称”的B树的叶节点链表也是为了让查找对称地往两端扩展。你能从“一棵树的镜像”出发去理解更复杂的平衡树结构这也算是刷题过程中顺带获得的额外收益。对于准备面试的你我的感受是不要只背代码把“递归比较的镜像配对逻辑”和“迭代用容器成对管理节点”这两个思维模型掌握好对称二叉树这一类题目就都能迎刃而解。遇到变体的第一反应也应该是“这道题的对称轴在哪哪两个节点需要被放在一起比较”想清楚这个代码自然就有了。做这道题时我自己有个小习惯每次写完对称二叉树就顺手把“相同的树”和“翻转二叉树”也写一遍因为三个题共享同一套递归骨架只是一两个参数方向不同。连续刷三题树递归的肌肉记忆会非常深刻。这种“打包练习”的方法比我当时一题一题单打独斗要高效得多。