刷算法题刷到树这一块的人基本都会跟力扣 101 这个编号碰面。它是力扣热题 100 里的常驻题也是技术面试里出现频率很高的“开场题”。题目描述短得离谱给你一棵二叉树判断它是不是镜像对称的。就这但真正到了白板手写的时候不少人会卡在递归参数怎么传、迭代版怎么处理空节点的问题上。这篇文章想跟你把这题彻底聊透从题目拆解到递归、迭代两种写法从复杂度复盘到边界用例最后把热题 100 里长得和它像的一串树题串起来。适合两类人看一类是刚开始刷二叉树、想找个靠谱模板的算法新人另一类是准备面试、想把这题变成稳定拿分项的人。读完之后你会发现对称二叉树不是靠背代码而是把“镜像”这两个字想明白了代码自然就出来了。1. 题目拆解对称到底比的是哪两棵子树1.1 原题信息与示例力扣第 101 题“对称二叉树”题目难度是简单但它在面试里被问到的频率一点都不“简单”。题面给一棵二叉树要求返回 true 表示这棵树是镜像对称的返回 false 表示不对称。所谓镜像对称通俗讲就是把树当成一张对着镜子的照片左边和右边应该互为倒影。对应的典型用例有三个对称示例[1,2,2,3,4,4,3]结构上看根节点 1 的左右孩子都是 2再往下左子树的左孩子 3 对着右子树的右孩子 3左子树的右孩子 4 对着右子树的左孩子 4。非对称示例[1,2,2,null,3,null,3]根节点往下左边缺左孩子右边缺右孩子明明左边多了一个右孩子 3右边也多了一个右孩子 3但镜像关系对不上。空树用例[]空树本身算对称。如果你是刷题新手可能会下意识地以为这题是“把左子树和右子树整棵树比较一下”。这个直觉对了一半但方向上必须做一次交叉这也是整道题唯一的灵魂。1.2 镜像对称的本质外侧对外侧内侧对内侧要理解对称二叉树最好的类比就是照镜子。你伸出左手镜子里伸出的是右手你把手从身体左侧挥到右侧镜子里是从右侧挥到左侧。具体到二叉树里根节点自己和自己对称不需要比较真正要比的是根节点的左孩子和右孩子。但往下递归时比较顺序必须反过来左子树的“外侧”也就是左孩子的左孩子要对应右子树的“外侧”也就是右孩子的右孩子。左子树的“内侧”也就是左孩子的右孩子要对应右子树的“内侧”也就是右孩子的左孩子。用一句话概括left.left和right.right比left.right和right.left比。这正是镜像和“相同”最本质的区别。如果把对称比较写成同向比较比如left.left对right.left那是在检查两棵子树是否结构完全一样而不是镜像关系结果就错了。1.3 一个反直觉的坑中序序列回文不代表对称我看到过不少人包括几年前的我自己试图走“取巧”路线把二叉树做中序遍历生成一个序列然后判断这个序列是不是回文。这个思路在多个示例上都能通过所以很有迷惑性。但坦率说它不是这道题的充要条件只是一个在特定形态下碰巧成立的“伪规律”。给一个反例。构造一棵树根节点值为 1左子树根节点值为 2左孩子值 5右孩子值 7右子树根节点值为 5左孩子值为 2而这个 2 的左孩子值 7。这棵树的中序遍历不包含空节点是[5,2,7,1,7,2,5]正着读反着读完全一样是标准回文。但你看结构根节点两侧的节点值都不一样左侧根是 2右侧根是 5这棵树显然不对称。原因在于中序遍历只保留了“值出现的先后顺序”丢掉了“左右孩子方向”的信息而恰好对称二叉树特别依赖方向。所以最稳妥的做法就是老老实实做“双节点成对比较”不要试图通过序列化偷懒。这也是面试官想看到的逻辑链条。2. 递归解法对称二叉树的标准写法2.1 递归三要素怎么拆递归题的思维方式就三件事终止条件、返回值定义、单层逻辑。这道题的递归函数最好不叫isSymmetric(root)而是设计成一个辅助函数接收两个节点p和q判断“这两个节点各自代表的子树位置是否镜像对称”。递归三要素拆下来是这样的终止条件 1p和q都是空节点说明同时走到头了这一组位置对称返回 true。终止条件 2p和q中只有一个为空说明一边有节点一边没有不可能镜像返回 false。单层逻辑先比p-val和q-val不相等直接 false相等了再递归检查p的左孩子配q的右孩子以及p的右孩子配q的左孩子两边同时成立才返回 true。这里有个细节值得强调终止条件的顺序不能乱。必须先判断“都为空”再判断“一个为空”最后才敢访问p-val和q-val。否则遇到空节点直接解引用程序就崩了。2.2 C 递归版完整代码力扣上 TreeNode 的定义是现成的一般不用重复写。这里我直接用类方法实现class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return check(root-left, root-right); } private: bool check(TreeNode* p, TreeNode* q) { // 两个位置都为空这一层是对称的 if (p nullptr q nullptr) return true; // 只有一个为空必然不对称 if (p nullptr || q nullptr) return false; // 值不相等肯定不对称 if (p-val ! q-val) return false; // 核心外侧对外侧内侧对内侧 return check(p-left, q-right) check(p-right, q-left); } };代码量很少但每一行都有明确的职责。主函数只需要处理空树的特殊情况真正的比较逻辑全在check里。这样设计的好处是清晰面试时也容易向面试官解释每一步在干什么。2.3 用对称样例手推一遍调用过程以对称示例[1,2,2,3,4,4,3]为例手动跑一遍递归能帮助理解为什么交叉比较是可行的。第一次调用check(root-left, root-right)传入的是两个值都为 2 的节点。两个节点值相等进入递归分支第一个分支check(left-left, right-right)也就是比较 3 和 3两者值相等它们的左右孩子都是空返回 true。第二个分支check(left-right, right-left)也就是比较 4 和 4同样都为空孩子返回 true。两个分支都返回 true运算得到 true最终整个函数返回 true。整个过程只做了三次双节点比较路径是完全确定的。你可以发现每一次递归实际上都在维护一个原则当前这两个节点应当是镜像位置上的节点那么它们的下一层也继续按照“外侧对外侧、内侧对内侧”推进。2.4 递归版最容易写错的两个点第一把交叉比成同向比。新手很容易写成check(p-left, q-left) check(p-right, q-right)这比较的是“两棵子树是否完全相同”而不是镜像。在少数用例里碰巧能过但一旦树的结构不对称立刻翻车。第二漏掉空节点判断或者把空节点判断顺序写反。p nullptr || q nullptr这个判断必须在访问p-val之前完成否则运行时告诉你空指针异常。我在力扣评论区见过不少人提交通过率高的测试却栽在空指针上基本都是这里顺序写错。如果想验证递归写得对不对最快的方式是拿两个示例跑一遍再补一个空树和一个只有一个节点的树。空节点处理没问题这道题的递归版基本就稳了。3. 迭代解法用队列模拟成对比较3.1 为什么需要迭代版递归版简洁但有些面试官会追问一句“如果树很深递归会不会栈溢出能不能用迭代实现” 这时候你需要拿出迭代版。迭代版的本质是用显式的数据结构模拟递归栈最常见的做法是用队列把“需要比较的两个节点”成对放进队列然后成对取出比较。用队列还有一个额外好处从根节点出发像逐层展开一样处理节点思路非常直观不容易出现递归边界混乱的问题。实际刷题时我也建议先写递归版拿到正确性再用迭代版练习“把递归改成非递归”的手感这对后面处理其他树的题很有帮助。3.2 队列版 C 完整代码class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; std::queueTreeNode* q; q.push(root-left); q.push(root-right); while (!q.empty()) { TreeNode* u q.front(); q.pop(); TreeNode* v q.front(); q.pop(); if (u nullptr v nullptr) continue; if (u nullptr || v nullptr) return false; if (u-val ! v-val) return false; // 交叉入队保持“成对比较”的顺序 q.push(u-left); q.push(v-right); q.push(u-right); q.push(v-left); } return true; } };每一步出队两个节点u和v它们必然是一对应该镜像的位置。跟递归版一样先处理空节点情况再比较值最后把它们的下一层孩子交叉入队。3.3 入队顺序的交叉逻辑代码里最容易困惑的是最后四行入队顺序。很多人会问为什么不是u-left和u-right一起入队因为队里相邻的两个节点需要配对比较。当前u是左侧某个节点v是右侧对应的镜像节点。下一步要比较的应该是u的外侧孩子u-left对应v的外侧孩子v-rightu的内侧孩子u-right对应v的内侧孩子v-left。所以入队顺序必须是u-left, v-right, u-right, v-left。这样每次弹出两个弹出的正好是一对。如果改成同向入队比如u-left, v-left拿出来的两个节点就不是镜像关系逻辑直接错误。这个顺序用对称样例验证一下就非常清楚根节点 1 的两个孩子都入队弹出2和2比较接着入队的是3左左和3右右、4左右和4右左后续弹出每一对都是正确的镜像位置。3.4 栈版变体与小结论队列能实现栈一样能实现。只需要把queue换成stack入栈顺序保持“成对”取出两个节点比较的逻辑完全不变。队列是按入队顺序逐个弹出栈是按后进先出弹出但因为每次都是成对入、成对出配对关系不会被破坏。我用栈跑过力扣的测试用例结果和队列版完全一致。这个变体通常不需要写在面试里但知道它能帮你理解“显式数据结构只是在模拟递归的节奏核心比较逻辑一致”。实际工作中如果遇到树特别深导致递归栈溢出的极端场景迭代版就是更稳的选择。4. 复杂度复盘与边界用例清单4.1 时间复杂度和空间复杂度对比对称二叉树这题无论递归还是迭代都要把整棵树的相关节点访问一遍。时间复杂度都是 O(n)n 是节点总数。空间复杂度取决于树的高度 h递归版调用深度是树高最坏情况下树退化成一条链h 接近 n空间复杂度 O(n)平均情况二叉树比较平衡空间复杂度 O(h)。迭代版的空间主要花在队列上队列里最多同时存在某一层的节点数乘 2最坏情况下是 O(n)。这里有一个容易误解的点递归版空间复杂度通常写 O(h)并不是说它比迭代版省空间而是因为很多教材默认讨论的是平衡二叉树。面试回答时建议主动区分“平均 h”和“最坏 n”两种情况会显得更有经验。下面这张表更方便对比解法时间复杂度空间复杂度是否容易栈溢出递归O(n)O(h)最坏 O(n)极端深树可能溢出迭代队列O(n)O(n)不会栈溢出迭代栈O(n)O(n)不会栈溢出4.2 空树、单节点、深层链表的边界情况写这道题时边界用例至少准备四类空树root nullptr直接是对称的这也是主函数开头判断空树的原因。只有一个根节点的树左右孩子都是空check(root-left, root-right)返回 true。根节点只有一个孩子的树比如[1,2]左孩子有值、右孩子为空递归到第二层发现一个空一个非空返回 false。深层链表形态的树比如每一层都只有一个节点往左延伸递归版在高度很大时可能栈溢出迭代版更安全。这些边界用例不需要全部写进代码但在面试手写时主动提一遍面试官会认为你想得足够周全。4.3 空指针与值比较的顺序问题我第一次写这个题的时候在迭代版本里犯过一个很低级的错误先比较u-val和v-val再判断空节点。结果空节点一出现就崩。正确的顺序永远是先判空再判值。这里有个小技巧把空节点判断合并成一套逻辑。u nullptr v nullptr是“都空则继续”u nullptr || v nullptr是“一个空则返回 false”。这两条连着写正好覆盖所有空节点组合逻辑上不重不漏。很多解法写得好的人并不是记忆力好而是靠这种“先穷举空节点的所有可能再进入值比较”的思维习惯。5. 从对称二叉树到力扣热题100树的题怎么串5.1 相同的树100和对称二叉树共用一套模板如果你先做了力扣第 100 题“相同的树”再回来做第 101 题会发现对称二叉树其实就是“相同的树”加了一个交叉动作。第 100 题比较两棵独立的树是不是完全相同递归逻辑是都空则 true一个空则 false值不等则 false递归比较p-left对q-leftp-right对q-right。第 101 题只是在最后一步把比较方向改成p-left对q-right、p-right对q-left。也就是说如果你掌握了“两个节点同时遍历”的递归模板100 和 101 都是同一套骨架。刷题时把这两道放一起做效率最高因为它们本质上在训练同一个核心能力成对访问节点并定义节点之间的比较关系。5.2 翻转二叉树226翻转和对称是孪生关系力扣第 226 题“翻转二叉树”是另一道与对称二叉树强相关的经典题。翻转的思路是把每个节点的左右孩子交换递归处理完整棵树。某种意义上翻转操作就是“制造镜像”而对称二叉树就是“验证镜像”。如果你能写出翻转函数那么判断对称二叉树还可以换一种思路先把右子树翻转再判断翻转后的右子树和左子树是否是同一棵树。这个思路在逻辑上是通的但实现上会多一步修改原树的副作用。如果面试时被问到“有没有其他解法”可以提这个思路但补充一句“实际更推荐双指针交叉比较因为不需要修改原树结构”会显得你有方案对比意识。热题 100 里树的题还有中序遍历、层序遍历、最大深度、最近公共祖先等它们并不是孤立的知识点。前序遍历和层序遍历能帮你快速生成序列辅助调试最大深度和最近公共祖先则是对递归返回值的进一步运用。先刷完 100、101、226、104再碰 199、236手感会顺畅很多。5.3 热题100相关树题刷题顺序建议我个人给刷力扣热题 100 的新手一个最精简的树题顺序题号题目核心考点104二叉树的最大深度递归终止条件与返回值累计100相同的树双节点成对递归模板101对称二叉树双节点交叉递归模板226翻转二叉树递归交换左右孩子102二叉树的层序遍历队列逐层扩展236二叉树的最近公共祖先递归返回节点信息这个顺序由易到难每道题都在复用前一道的核心技能。101 放在 100 后面因为交叉比较是在同向比较的基础上做一次方向调整理解起来最自然。刷完这六道你对二叉树的递归和迭代都会建立比较扎实的肌肉记忆。5.4 通用双节点比较模板最后我把这套双节点比较模板单独提取出来方便你记也方便你做其他变体题时套用比较两个节点 p 和 q 是否满足某种关系 1. 都为空 - 当前关系成立 2. 一个为空 - 当前关系不成立 3. 值不满足条件 - 当前关系不成立 4. 递归检查 p 和 q 的下一层节点关系定义随题目变化。这个模板是“相同的树”“对称二叉树”“子树判断”等一大类题目的共同底层结构。把模板背下来不难难的是知道第四步该往哪个方向递归。对称二叉树考的就是第四步的方向感方向对了题就秒了。6. 刷题避坑记录与调试技巧6.1 我踩过的典型坑第一个坑只在isSymmetric里比较了root-left root-right。这个连等于号都经常写错比较的是指针地址而不是节点值。更关键的是这样只比较一层完全没有往下递归很多非对称用例测不出来。正确的逻辑必须下沉到check函数里逐层比较。第二个坑递归时把“外侧对外侧”的交叉关系搞混。我在 2.4 里已经提过这里再补充一个记忆技巧你只需要牢牢记住一个词“交叉”。只要看到是镜像对称递归参数里永远带交叉check(p-left, q-right)和check(p-right, q-left)不要带同向参数。如果哪次忘记了现场拿一个最简单的非对称树手推一步就能纠正自己。第三个坑迭代版里忘记处理空节点连续的情况。前面代码里有一句if (u nullptr v nullptr) continue;这句话不能省。如果两个空节点入队后不做处理就继续比较值必然空指针异常。而且如果不continue下一步去访问空节点的孩子也会崩溃。处理空树、只处理一层树的用例能帮你快速暴露这个问题。6.2 调试树的实用技巧调试二叉树问题我强烈建议自己写一个层序输出函数把树的结构打印出来。比如判断对称二叉树时可以按层打印每个节点缺失的用#代替这样结构问题一眼就能看出来。有一次我提交的代码在示例上全对但在一个隐藏用例上报错。我把那个用例转成层序数组一看发现树里有很多空节点而我的迭代版在处理连续多个空节点时顺序乱了。当时如果没有打印函数我可能要盯着代码猜很久。调试技巧虽然简单实际刷题时帮你省的时间是实打实的。6.3 个人向经验怎么把对称二叉树变成秒杀题我自己的体会是对称二叉树这道题是二叉树递归思维的“分水岭”。它既不像最大深度那样只关注返回值也不像层序遍历那样需要额外维护层级信息它恰好卡在“递归参数怎么设计”这个最核心的位置上。把这一题吃透后面再做最近公共祖先、树的序列化这类更复杂的题你会发现它们都在考同一件事递归函数到底接收什么参数、返回什么信息。最后再分享一个小建议。刷完力扣 101 之后不要急着下一道新题花十分钟用自己的话把这个递归逻辑讲一遍。讲得出来才是真会了讲着讲着卡壳的地方就是你还没真正理解的薄弱点。自己给自己做复盘效果远好于疯狂刷同类型的新题。这题放在热题 100 里既是对二叉树的入门检验也是对你递归功底的直接考核。把它当成模板题反复练直到两道解法都能不看代码写出来你的二叉树刷题手感会有一个质的提升。
刷算法题刷到树这一块的人基本都会跟力扣 101 这个编号碰面。它是力扣热题 100 里的常驻题也是技术面试里出现频率很高的“开场题”。题目描述短得离谱给你一棵二叉树判断它是不是镜像对称的。就这但真正到了白板手写的时候不少人会卡在递归参数怎么传、迭代版怎么处理空节点的问题上。这篇文章想跟你把这题彻底聊透从题目拆解到递归、迭代两种写法从复杂度复盘到边界用例最后把热题 100 里长得和它像的一串树题串起来。适合两类人看一类是刚开始刷二叉树、想找个靠谱模板的算法新人另一类是准备面试、想把这题变成稳定拿分项的人。读完之后你会发现对称二叉树不是靠背代码而是把“镜像”这两个字想明白了代码自然就出来了。1. 题目拆解对称到底比的是哪两棵子树1.1 原题信息与示例力扣第 101 题“对称二叉树”题目难度是简单但它在面试里被问到的频率一点都不“简单”。题面给一棵二叉树要求返回 true 表示这棵树是镜像对称的返回 false 表示不对称。所谓镜像对称通俗讲就是把树当成一张对着镜子的照片左边和右边应该互为倒影。对应的典型用例有三个对称示例[1,2,2,3,4,4,3]结构上看根节点 1 的左右孩子都是 2再往下左子树的左孩子 3 对着右子树的右孩子 3左子树的右孩子 4 对着右子树的左孩子 4。非对称示例[1,2,2,null,3,null,3]根节点往下左边缺左孩子右边缺右孩子明明左边多了一个右孩子 3右边也多了一个右孩子 3但镜像关系对不上。空树用例[]空树本身算对称。如果你是刷题新手可能会下意识地以为这题是“把左子树和右子树整棵树比较一下”。这个直觉对了一半但方向上必须做一次交叉这也是整道题唯一的灵魂。1.2 镜像对称的本质外侧对外侧内侧对内侧要理解对称二叉树最好的类比就是照镜子。你伸出左手镜子里伸出的是右手你把手从身体左侧挥到右侧镜子里是从右侧挥到左侧。具体到二叉树里根节点自己和自己对称不需要比较真正要比的是根节点的左孩子和右孩子。但往下递归时比较顺序必须反过来左子树的“外侧”也就是左孩子的左孩子要对应右子树的“外侧”也就是右孩子的右孩子。左子树的“内侧”也就是左孩子的右孩子要对应右子树的“内侧”也就是右孩子的左孩子。用一句话概括left.left和right.right比left.right和right.left比。这正是镜像和“相同”最本质的区别。如果把对称比较写成同向比较比如left.left对right.left那是在检查两棵子树是否结构完全一样而不是镜像关系结果就错了。1.3 一个反直觉的坑中序序列回文不代表对称我看到过不少人包括几年前的我自己试图走“取巧”路线把二叉树做中序遍历生成一个序列然后判断这个序列是不是回文。这个思路在多个示例上都能通过所以很有迷惑性。但坦率说它不是这道题的充要条件只是一个在特定形态下碰巧成立的“伪规律”。给一个反例。构造一棵树根节点值为 1左子树根节点值为 2左孩子值 5右孩子值 7右子树根节点值为 5左孩子值为 2而这个 2 的左孩子值 7。这棵树的中序遍历不包含空节点是[5,2,7,1,7,2,5]正着读反着读完全一样是标准回文。但你看结构根节点两侧的节点值都不一样左侧根是 2右侧根是 5这棵树显然不对称。原因在于中序遍历只保留了“值出现的先后顺序”丢掉了“左右孩子方向”的信息而恰好对称二叉树特别依赖方向。所以最稳妥的做法就是老老实实做“双节点成对比较”不要试图通过序列化偷懒。这也是面试官想看到的逻辑链条。2. 递归解法对称二叉树的标准写法2.1 递归三要素怎么拆递归题的思维方式就三件事终止条件、返回值定义、单层逻辑。这道题的递归函数最好不叫isSymmetric(root)而是设计成一个辅助函数接收两个节点p和q判断“这两个节点各自代表的子树位置是否镜像对称”。递归三要素拆下来是这样的终止条件 1p和q都是空节点说明同时走到头了这一组位置对称返回 true。终止条件 2p和q中只有一个为空说明一边有节点一边没有不可能镜像返回 false。单层逻辑先比p-val和q-val不相等直接 false相等了再递归检查p的左孩子配q的右孩子以及p的右孩子配q的左孩子两边同时成立才返回 true。这里有个细节值得强调终止条件的顺序不能乱。必须先判断“都为空”再判断“一个为空”最后才敢访问p-val和q-val。否则遇到空节点直接解引用程序就崩了。2.2 C 递归版完整代码力扣上 TreeNode 的定义是现成的一般不用重复写。这里我直接用类方法实现class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return check(root-left, root-right); } private: bool check(TreeNode* p, TreeNode* q) { // 两个位置都为空这一层是对称的 if (p nullptr q nullptr) return true; // 只有一个为空必然不对称 if (p nullptr || q nullptr) return false; // 值不相等肯定不对称 if (p-val ! q-val) return false; // 核心外侧对外侧内侧对内侧 return check(p-left, q-right) check(p-right, q-left); } };代码量很少但每一行都有明确的职责。主函数只需要处理空树的特殊情况真正的比较逻辑全在check里。这样设计的好处是清晰面试时也容易向面试官解释每一步在干什么。2.3 用对称样例手推一遍调用过程以对称示例[1,2,2,3,4,4,3]为例手动跑一遍递归能帮助理解为什么交叉比较是可行的。第一次调用check(root-left, root-right)传入的是两个值都为 2 的节点。两个节点值相等进入递归分支第一个分支check(left-left, right-right)也就是比较 3 和 3两者值相等它们的左右孩子都是空返回 true。第二个分支check(left-right, right-left)也就是比较 4 和 4同样都为空孩子返回 true。两个分支都返回 true运算得到 true最终整个函数返回 true。整个过程只做了三次双节点比较路径是完全确定的。你可以发现每一次递归实际上都在维护一个原则当前这两个节点应当是镜像位置上的节点那么它们的下一层也继续按照“外侧对外侧、内侧对内侧”推进。2.4 递归版最容易写错的两个点第一把交叉比成同向比。新手很容易写成check(p-left, q-left) check(p-right, q-right)这比较的是“两棵子树是否完全相同”而不是镜像。在少数用例里碰巧能过但一旦树的结构不对称立刻翻车。第二漏掉空节点判断或者把空节点判断顺序写反。p nullptr || q nullptr这个判断必须在访问p-val之前完成否则运行时告诉你空指针异常。我在力扣评论区见过不少人提交通过率高的测试却栽在空指针上基本都是这里顺序写错。如果想验证递归写得对不对最快的方式是拿两个示例跑一遍再补一个空树和一个只有一个节点的树。空节点处理没问题这道题的递归版基本就稳了。3. 迭代解法用队列模拟成对比较3.1 为什么需要迭代版递归版简洁但有些面试官会追问一句“如果树很深递归会不会栈溢出能不能用迭代实现” 这时候你需要拿出迭代版。迭代版的本质是用显式的数据结构模拟递归栈最常见的做法是用队列把“需要比较的两个节点”成对放进队列然后成对取出比较。用队列还有一个额外好处从根节点出发像逐层展开一样处理节点思路非常直观不容易出现递归边界混乱的问题。实际刷题时我也建议先写递归版拿到正确性再用迭代版练习“把递归改成非递归”的手感这对后面处理其他树的题很有帮助。3.2 队列版 C 完整代码class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; std::queueTreeNode* q; q.push(root-left); q.push(root-right); while (!q.empty()) { TreeNode* u q.front(); q.pop(); TreeNode* v q.front(); q.pop(); if (u nullptr v nullptr) continue; if (u nullptr || v nullptr) return false; if (u-val ! v-val) return false; // 交叉入队保持“成对比较”的顺序 q.push(u-left); q.push(v-right); q.push(u-right); q.push(v-left); } return true; } };每一步出队两个节点u和v它们必然是一对应该镜像的位置。跟递归版一样先处理空节点情况再比较值最后把它们的下一层孩子交叉入队。3.3 入队顺序的交叉逻辑代码里最容易困惑的是最后四行入队顺序。很多人会问为什么不是u-left和u-right一起入队因为队里相邻的两个节点需要配对比较。当前u是左侧某个节点v是右侧对应的镜像节点。下一步要比较的应该是u的外侧孩子u-left对应v的外侧孩子v-rightu的内侧孩子u-right对应v的内侧孩子v-left。所以入队顺序必须是u-left, v-right, u-right, v-left。这样每次弹出两个弹出的正好是一对。如果改成同向入队比如u-left, v-left拿出来的两个节点就不是镜像关系逻辑直接错误。这个顺序用对称样例验证一下就非常清楚根节点 1 的两个孩子都入队弹出2和2比较接着入队的是3左左和3右右、4左右和4右左后续弹出每一对都是正确的镜像位置。3.4 栈版变体与小结论队列能实现栈一样能实现。只需要把queue换成stack入栈顺序保持“成对”取出两个节点比较的逻辑完全不变。队列是按入队顺序逐个弹出栈是按后进先出弹出但因为每次都是成对入、成对出配对关系不会被破坏。我用栈跑过力扣的测试用例结果和队列版完全一致。这个变体通常不需要写在面试里但知道它能帮你理解“显式数据结构只是在模拟递归的节奏核心比较逻辑一致”。实际工作中如果遇到树特别深导致递归栈溢出的极端场景迭代版就是更稳的选择。4. 复杂度复盘与边界用例清单4.1 时间复杂度和空间复杂度对比对称二叉树这题无论递归还是迭代都要把整棵树的相关节点访问一遍。时间复杂度都是 O(n)n 是节点总数。空间复杂度取决于树的高度 h递归版调用深度是树高最坏情况下树退化成一条链h 接近 n空间复杂度 O(n)平均情况二叉树比较平衡空间复杂度 O(h)。迭代版的空间主要花在队列上队列里最多同时存在某一层的节点数乘 2最坏情况下是 O(n)。这里有一个容易误解的点递归版空间复杂度通常写 O(h)并不是说它比迭代版省空间而是因为很多教材默认讨论的是平衡二叉树。面试回答时建议主动区分“平均 h”和“最坏 n”两种情况会显得更有经验。下面这张表更方便对比解法时间复杂度空间复杂度是否容易栈溢出递归O(n)O(h)最坏 O(n)极端深树可能溢出迭代队列O(n)O(n)不会栈溢出迭代栈O(n)O(n)不会栈溢出4.2 空树、单节点、深层链表的边界情况写这道题时边界用例至少准备四类空树root nullptr直接是对称的这也是主函数开头判断空树的原因。只有一个根节点的树左右孩子都是空check(root-left, root-right)返回 true。根节点只有一个孩子的树比如[1,2]左孩子有值、右孩子为空递归到第二层发现一个空一个非空返回 false。深层链表形态的树比如每一层都只有一个节点往左延伸递归版在高度很大时可能栈溢出迭代版更安全。这些边界用例不需要全部写进代码但在面试手写时主动提一遍面试官会认为你想得足够周全。4.3 空指针与值比较的顺序问题我第一次写这个题的时候在迭代版本里犯过一个很低级的错误先比较u-val和v-val再判断空节点。结果空节点一出现就崩。正确的顺序永远是先判空再判值。这里有个小技巧把空节点判断合并成一套逻辑。u nullptr v nullptr是“都空则继续”u nullptr || v nullptr是“一个空则返回 false”。这两条连着写正好覆盖所有空节点组合逻辑上不重不漏。很多解法写得好的人并不是记忆力好而是靠这种“先穷举空节点的所有可能再进入值比较”的思维习惯。5. 从对称二叉树到力扣热题100树的题怎么串5.1 相同的树100和对称二叉树共用一套模板如果你先做了力扣第 100 题“相同的树”再回来做第 101 题会发现对称二叉树其实就是“相同的树”加了一个交叉动作。第 100 题比较两棵独立的树是不是完全相同递归逻辑是都空则 true一个空则 false值不等则 false递归比较p-left对q-leftp-right对q-right。第 101 题只是在最后一步把比较方向改成p-left对q-right、p-right对q-left。也就是说如果你掌握了“两个节点同时遍历”的递归模板100 和 101 都是同一套骨架。刷题时把这两道放一起做效率最高因为它们本质上在训练同一个核心能力成对访问节点并定义节点之间的比较关系。5.2 翻转二叉树226翻转和对称是孪生关系力扣第 226 题“翻转二叉树”是另一道与对称二叉树强相关的经典题。翻转的思路是把每个节点的左右孩子交换递归处理完整棵树。某种意义上翻转操作就是“制造镜像”而对称二叉树就是“验证镜像”。如果你能写出翻转函数那么判断对称二叉树还可以换一种思路先把右子树翻转再判断翻转后的右子树和左子树是否是同一棵树。这个思路在逻辑上是通的但实现上会多一步修改原树的副作用。如果面试时被问到“有没有其他解法”可以提这个思路但补充一句“实际更推荐双指针交叉比较因为不需要修改原树结构”会显得你有方案对比意识。热题 100 里树的题还有中序遍历、层序遍历、最大深度、最近公共祖先等它们并不是孤立的知识点。前序遍历和层序遍历能帮你快速生成序列辅助调试最大深度和最近公共祖先则是对递归返回值的进一步运用。先刷完 100、101、226、104再碰 199、236手感会顺畅很多。5.3 热题100相关树题刷题顺序建议我个人给刷力扣热题 100 的新手一个最精简的树题顺序题号题目核心考点104二叉树的最大深度递归终止条件与返回值累计100相同的树双节点成对递归模板101对称二叉树双节点交叉递归模板226翻转二叉树递归交换左右孩子102二叉树的层序遍历队列逐层扩展236二叉树的最近公共祖先递归返回节点信息这个顺序由易到难每道题都在复用前一道的核心技能。101 放在 100 后面因为交叉比较是在同向比较的基础上做一次方向调整理解起来最自然。刷完这六道你对二叉树的递归和迭代都会建立比较扎实的肌肉记忆。5.4 通用双节点比较模板最后我把这套双节点比较模板单独提取出来方便你记也方便你做其他变体题时套用比较两个节点 p 和 q 是否满足某种关系 1. 都为空 - 当前关系成立 2. 一个为空 - 当前关系不成立 3. 值不满足条件 - 当前关系不成立 4. 递归检查 p 和 q 的下一层节点关系定义随题目变化。这个模板是“相同的树”“对称二叉树”“子树判断”等一大类题目的共同底层结构。把模板背下来不难难的是知道第四步该往哪个方向递归。对称二叉树考的就是第四步的方向感方向对了题就秒了。6. 刷题避坑记录与调试技巧6.1 我踩过的典型坑第一个坑只在isSymmetric里比较了root-left root-right。这个连等于号都经常写错比较的是指针地址而不是节点值。更关键的是这样只比较一层完全没有往下递归很多非对称用例测不出来。正确的逻辑必须下沉到check函数里逐层比较。第二个坑递归时把“外侧对外侧”的交叉关系搞混。我在 2.4 里已经提过这里再补充一个记忆技巧你只需要牢牢记住一个词“交叉”。只要看到是镜像对称递归参数里永远带交叉check(p-left, q-right)和check(p-right, q-left)不要带同向参数。如果哪次忘记了现场拿一个最简单的非对称树手推一步就能纠正自己。第三个坑迭代版里忘记处理空节点连续的情况。前面代码里有一句if (u nullptr v nullptr) continue;这句话不能省。如果两个空节点入队后不做处理就继续比较值必然空指针异常。而且如果不continue下一步去访问空节点的孩子也会崩溃。处理空树、只处理一层树的用例能帮你快速暴露这个问题。6.2 调试树的实用技巧调试二叉树问题我强烈建议自己写一个层序输出函数把树的结构打印出来。比如判断对称二叉树时可以按层打印每个节点缺失的用#代替这样结构问题一眼就能看出来。有一次我提交的代码在示例上全对但在一个隐藏用例上报错。我把那个用例转成层序数组一看发现树里有很多空节点而我的迭代版在处理连续多个空节点时顺序乱了。当时如果没有打印函数我可能要盯着代码猜很久。调试技巧虽然简单实际刷题时帮你省的时间是实打实的。6.3 个人向经验怎么把对称二叉树变成秒杀题我自己的体会是对称二叉树这道题是二叉树递归思维的“分水岭”。它既不像最大深度那样只关注返回值也不像层序遍历那样需要额外维护层级信息它恰好卡在“递归参数怎么设计”这个最核心的位置上。把这一题吃透后面再做最近公共祖先、树的序列化这类更复杂的题你会发现它们都在考同一件事递归函数到底接收什么参数、返回什么信息。最后再分享一个小建议。刷完力扣 101 之后不要急着下一道新题花十分钟用自己的话把这个递归逻辑讲一遍。讲得出来才是真会了讲着讲着卡壳的地方就是你还没真正理解的薄弱点。自己给自己做复盘效果远好于疯狂刷同类型的新题。这题放在热题 100 里既是对二叉树的入门检验也是对你递归功底的直接考核。把它当成模板题反复练直到两道解法都能不看代码写出来你的二叉树刷题手感会有一个质的提升。
