文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文是「InterviewGuide」开源仓库中 LeetCode 树专题 Easy 题目笔记 的深度解读。围绕经典面试题「剑指 Offer 28. 对称的二叉树」从题目定义、对称性判定标准出发完整还原仓库笔记中记录的三种解法两种递归法、一种迭代法并结合仓库内 剑指 Offer 系列同题笔记 的另一种同思路实现帮你彻底吃透树的对称性判断这一高频考点。一、题目速览什么是一棵对称的二叉树原题出自力扣剑指 Offer 28. 对称的二叉树仓库笔记中给出了力扣原题链接对应牛客网版本为 No58、对称的二叉树收录于 剑指 Offer 全集。题目要求请实现一个函数用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样那么它是对称的。对称的含义一棵二叉树对称等价于这棵树和它的镜像完全相同。注意这里的镜像指的是水平翻转后的树而不是单纯的左右子树值相等——它要求左子树的左孩子 与 右子树的右孩子对应、左子树的右孩子 与 右子树的左孩子对应逐层、逐节点镜像相等。1. 对称的例子例如二叉树[1,2,2,3,4,4,3]是对称的1 / \ 2 2 / \ / \ 3 4 4 3从根节点1出发左子树根2与右子树根2值相等再往下一层左子树的左孩子3与右子树的右孩子3对应左子树的右孩子4与右子树的左孩子4对应完全镜像匹配。2. 不对称的例子而下面这个[1,2,2,null,3,null,3]则不是镜像对称的1 / \ 2 2 \ \ 3 3虽然两个子树根节点都是2但左子树缺失了左孩子、只有右孩子3右子树缺失了右孩子、只有左孩子3。若按镜像规则左子树的左孩子应当与右子树的右孩子对应此处却是null对null表面匹配而左子树的右孩子3应当与右子树的左孩子对应——右子树却没有左孩子位置错位导致不对称。这也是迭代法中需要格外警惕的值相等但位置不对陷阱。3. 示例与限制示例 1输入root [1,2,2,3,4,4,3] 输出true示例 2输入root [1,2,2,null,3,null,3] 输出false限制0 节点个数 1000注意节点个数可能为 0即空树root nullptr。从对称性的定义看空树没有左右子树需要比对视为对称返回true。二、核心思路把一棵树的对称转化为两棵子树的镜像相等判断整棵树是否对称本质上是一个双指针比较问题我们并不比较同一个节点的左右孩子那是左右子树相等不是对称而是比较根节点的左子树 与 右子树是否互为镜像。为此需要抽象出一个辅助函数isEqual(node1, node2)它的语义是判断以 node1 为根的树 与 以 node2 为根的树 是否互为镜像。判断规则只有三条两棵子树都为空nullptr与nullptr互为镜像返回true两棵子树一空一非空结构都不匹配返回false两棵子树都不空先比较当前节点值node1-val node2-val值相等后再递归判断node1的左孩子与node2的右孩子镜像对应、node1的右孩子与node2的左孩子镜像对应两者同时成立才返回true。主函数isSymmetric(root)只需处理空树然后调用isEqual(root-left, root-right)即可。下面仓库笔记中记录的三种写法都是在这个框架下展开的。三、解法一递归法基础版这是仓库笔记中给出的第一种实现逻辑最直白、最适合面试时先讲清楚思路bool isEqual(TreeNode* node1, TreeNode* node2) { if (node1 nullptr node2 nullptr) return true; if (node1 nullptr node2 ! nullptr) return false; if (node2 nullptr node1 ! nullptr) return false; if (node1-val node2-val) { return isEqual(node1-left, node2-right) isEqual(node1-right, node2-left); } else return false; } bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return isEqual(root-left, root-right); }逐行解读第一行判断双空这是递归的终止条件之一比较到叶子之下的nullptr层两侧都是空说明此前所有路径都镜像匹配返回true第二、三行分别处理node1 空但 node2 非空node2 空但 node1 非空两种情况只要一侧为空另一侧不为空结构就不对称直接返回false第四行两侧节点都存在且值相等才继续向下比较值不相等则返回false递归式isEqual(node1-left, node2-right) isEqual(node1-right, node2-left)是对称判定的灵魂左对右、右对左正是镜像二字的代码化表达。具备短路特性左侧一旦返回false右侧就不会再递归能提前剪枝。复杂度分析每个节点至多被访问一次时间复杂度 O(n)n 为节点个数题目限制 0 n 1000递归深度取决于树高最坏情况下退化成链为 O(n)空间复杂度 O(n)平均情况下为 O(log n)。仓库笔记中该实现的实测表现为执行用时 12 ms在所有 C 提交中击败了 32.98% 的用户内存消耗 16.3 MB击败 100.00% 的用户该数据为笔记作者提交当时的 LeetCode 环境实测仅作参考不同时期提交结果会有波动。四、解法二递归法精简改进版基础版的空判断写了三行其实可以合并。仓库笔记中的第二种写法把一空一非空两种情况合并成一行代码更紧凑bool isEqual(TreeNode* node1, TreeNode* node2) { if (node1 nullptr node2 nullptr) return true; if (node1 nullptr || node2 nullptr) return false; // 减少判断 if (node1-val node2-val) { return isEqual(node1-left, node2-right) isEqual(node1-right, node2-left); } else return false; } bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return isEqual(root-left, root-right); }改进点分析if (node1 nullptr || node2 nullptr) return false;一行同时覆盖了基础版中两个分支前面已经排除了双空因此走到这一行时只要有一侧为空必然是一空一非空直接返回false即可其余逻辑与解法一完全一致但分支更少、判断次数更少代码可读性和执行效率都略有提升。仓库笔记中该实现的实测表现为执行用时 8 ms在所有 C 提交中击败了 67.83% 的用户内存消耗 16.4 MB击败 100.00% 的用户。这个精简版在仓库的剑指 Offer 系列笔记 58-剑指offer.md 中还有一次同思路的强化——二刷时作者进一步把值不相等提前返回代码更为紧凑bool isEqual(TreeNode* node1, TreeNode* node2) { if (node1 nullptr node2 nullptr) return true; if (node1 nullptr || node2 nullptr) return false; if (node1-val ! node2-val) return false; return isEqual(node1-left, node2-right) isEqual(node1-right, node2-left); } bool isSymmetrical(TreeNode* pRoot) { if (pRoot nullptr) return true; return isEqual(pRoot-left, pRoot-right); }可见在牛客网版本的isSymmetrical中作者将值不等用!直接短路返回减少了if/else嵌套层级。两处实现相互印证无论力扣版还是牛客版递归判对称的骨架完全一致差别仅在空判断与值判断的写法组织上。这也是递归类二叉树题最常见的面试演进路径——先把思路讲对再谈精简。五、解法三迭代法借助队列按层比对递归之外仓库笔记还记录了一种迭代实现。思路是利用队列做层序遍历把每一层所有节点的左右孩子包括空指针收集进一个临时数组然后从数组两端向中间做镜像比对。作者在笔记中标注太麻烦了不值得借鉴但它对理解值相等但结构不对称的边界情况非常有帮助面试时也可以作为递归之外我还会迭代的能力展示。bool isSymmetric(TreeNode* root) { if (!root) { return true; } queueTreeNode * que1; que1.push(root); while (!que1.empty()) { int size que1.size(); vectorTreeNode * tmp; // 判断虽然不是镜像节点但是值依然相等的情况比如上述情况 while (size 0) { TreeNode *fronts que1.front(); que1.pop(); tmp.push_back(fronts-left); if (fronts-left) { que1.push(fronts-left); } tmp.push_back(fronts-right); if (fronts-right) { que1.push(fronts-right); } size--; } int i 0; int j tmp.size() - 1; while (i j) { if (tmp[i] ! nullptr tmp[j] ! nullptr) { if (tmp[i]-val ! tmp[j]-val) { return false; } } else if (tmp[i] nullptr tmp[j] nullptr) { // 两侧都为空继续比较下一对 } else { return false; } i; j--; } } return true; }执行流程拆解空树直接返回true把根节点入队进入层序遍历外层循环记录当前层节点数size内层循环逐一出队并把每个节点的left、right原样包括 nullptr压入临时数组tmp同时把非空孩子重新入队供下一层使用。这一步的关键是空指针也要占位否则下一层无法从位置上做镜像比对本层收集完毕后用双指针i、j从tmp两端向中间扫描两侧都非空则比val值不等返回false一空一非空返回false双空则继续所有层都通过比对最终返回true。为什么需要临时数组 tmp笔记注释点出了要害判断虽然不是镜像节点但是值依然相等的情况。例如题目中的反例1 / \ 2 2 \ \ 3 3第二层的两个孩子都是2值相等但如果只比这一层从左到右的值序列[2,2]本身是对称的会误判为对称。只有把第三层的空位也纳入左子树的左孩子为null、右子树的左孩子为null序列为[null,3,null,3]才能发现tmp[0]与tmp[3]是空对非空从而正确判为不对称。这正是迭代法相对递归法更繁琐、更容易踩坑的地方也是作者评价其太麻烦、不值得借鉴的原因。复杂度分析每个节点同样至多访问一次时间 O(n)需要队列与临时数组存储节点空间 O(n)。六、三种解法对比与面试建议维度解法一递归基础版解法二递归精简版解法三迭代法思路左右子树互为镜像递归比对同上合并空判断分支层序遍历 双指针镜像比对代码量较多三个空判断分支最少\|\|合并空判断最多队列 临时数组时间复杂度O(n)O(n)O(n)空间复杂度O(h)h 为树高O(h)h 为树高O(n)风险点分支冗余易写漏需理解\|\|前已排除双空空指针占位易错易误判值等位错作者评价直白易懂推荐太麻烦了不值得借鉴面试建议首选递归先讲清楚比较左子树的左孩子与右子树的右孩子、左子树的右孩子与右子树的左孩子这一镜像判定核心再给出解法二这种精简实现展示代码组织能力务必处理空树题目限制节点数可为 0root nullptr时返回true这一点仓库笔记与剑指 Offer 笔记两处实现都专门写了注释强调能讲清迭代作为加分项如果你能指出迭代法需要空指针占位 双指针比对并说明[1,2,2,null,3,null,3]这类反例为何会迷惑只看值的写法会让面试官确认你是真懂而不是背题横向关联对称判断与 面试题26.树的子结构、面试题07.重建二叉树 一样都属于树的递归结构比较家族掌握了递归比较两棵子树的范式这类题可以一通百通。七、仓库定位与延伸阅读本笔记收录于 InterviewGuide 仓库的 LeetCode 树专题 Easy 分类下同专题还整理了序列化二叉树、二叉树的前/中/后序遍历、二叉搜索树第 k 大节点等一系列高频树题本题的牛客网版本则位于 剑指 Offer 系列 No58两处解法可对照阅读。此外仓库的 02-sword-offer 目录收录了完整剑指 Offer 题解03-leetcode 目录则按专题整理了精选力扣题目适合校招、社招算法复习时系统刷题。核心结论回顾判断二叉树对称本质是判断左子树与右子树互为镜像递归解法用isEqual(node1-left, node2-right) isEqual(node1-right, node2-left)一句话点破镜像关系迭代解法则通过层序收集 双指针比对处理值等位错的陷阱。从基础版到精简版再到迭代版这一题完整覆盖了二叉树递归比较问题的思考路径值得作为树专题的入门必刷题反复咀嚼。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐StarRocks CORR 函数实战计算两列数据的皮尔逊相关系数StarRocks CORR 函数实战计算两列数据的皮尔逊相关系数 StarRocks 的 CORR 聚合函数用于计算两个表达式之间的皮尔逊相关系数Pear教程InterviewGuide 刷题笔记剑指 Offer 28「对称的二叉树」递归与迭代全解法剖析InterviewGuide 刷题笔记剑指 Offer 28「对称的二叉树」递归与迭代全解法剖析 本篇是 InterviewGuide 仓库中「 精选力扣 3文档教程知识库Eclipse Mosquitto 0.8.2 缺陷修复版本深度解析loop 超时、消息队列与 QoS 重试逻辑Eclipse Mosquitto 0.8.2 缺陷修复版本深度解析loop 超时、消息队列与 QoS 重试逻辑 Mosquitto 0.8.2 是 Ecli教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
