教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本文围绕 YCBlogs 算法专栏 leetcode/05.树/18.对称的二叉树.md 展开讲解如何判断一棵二叉树是否对称这一经典树算法题从题目定义出发介绍核心的对称前序遍历判定思路并给出可直接运行的递归解法、队列迭代解法与序列比较解法。读完本文你将掌握对称二叉树的三种判定实现、各自的边界处理要点以及它们与二叉树遍历、镜像操作之间的内在联系。01 题目要求什么是对称的二叉树原文档给出的题目描述如下请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样那么它是对称的。所谓对称的二叉树可以直观理解为以根节点为轴把整棵树沿中轴线对折左右两侧完全重合。例如下面这棵树就是对称的8 / \ 6 6 / \ / \ 5 7 7 5判断规则可以递归地表述为根节点的左右子树互为镜像左子树的左孩子与右子树的右孩子对应左子树的右孩子与右子树的左孩子对应对应节点的值必须相等且对应的空节点位置也必须一一吻合。和它的镜像一样这个定义直接指向了本仓库中另一篇姊妹题 leetcode/05.树/22.二叉树的镜像.md只要实现了生成二叉树镜像的函数mirror理论上就可以通过原树与镜像树逐节点比较来判断对称性——当然更高效的做法是下文介绍的成对比较递归它不必真的先生成镜像。02 前置知识节点结构与三种遍历在展开解法之前先回顾与本题直接相关的两个基础知识点。2.1 二叉树的节点定义原文档的实例代码中节点采用典型的二叉链表表示private static class BinaryTreeNode { private int val; // 节点值 private BinaryTreeNode left; // 左孩子 private BinaryTreeNode right; // 右孩子 public BinaryTreeNode() { } public BinaryTreeNode(int val) { this.val val; } Override public String toString() { return val ; } }这与 leetcode/05.树/02.实现二叉树.md 中二叉查找树节点BSTNode的key / left / right / parent结构一脉相承区别仅在于对称判定不需要parent指针。2.2 三种经典遍历二叉树有三种经典遍历方式参见 leetcode/05.树/01.二叉树简介.md 与 leetcode/05.树/02.实现二叉树.md前序遍历先访问父节点再遍历左子树最后遍历右子树父 → 左 → 右中序遍历先遍历左子树再访问父节点最后遍历右子树左 → 父 → 右后序遍历先遍历左子树再遍历右子树最后访问父节点左 → 右 → 父。可以注意到一个共同点这三种遍历都是先左后右——在递归定义中左子树总是先于右子树被访问。这正是对称判定需要突破的思维定式。03 核心思路定义对称遍历与序列比较3.1 原文档的判定思想原文档的问题分析给出了一个非常巧妙的角度通常我们有三种不同的二叉树遍历算法即前序遍历、中序遍历和后序遍历。在这三种遍历算法中都是先遍历左子结点再遍历右子结点。我们是否可以定义一种遍历算法先遍历右子结点再遍历左子结点比如我们针对前序遍历定义一种对称的遍历算法即先遍历父节点再遍历它的右子结点最后遍历它的左子结点。据此可以得到前序遍历序列按父 → 左 → 右顺序访问得到的节点序列对称前序遍历序列按父 → 右 → 左顺序访问得到的节点序列。由于先父后右后左恰好等于把镜像树做普通前序遍历的结果因此一棵二叉树对称当且仅当它的前序遍历序列与对称前序遍历序列完全相同。以对称树为例验证8 / \ 6 6 / \ / \ 5 7 7 5前序遍历父 → 左 → 右8, 6, 5, 7, 6, 7, 5对称前序遍历父 → 右 → 左8, 6, 5, 7, 6, 7, 5两个序列一致判定为对称与肉眼观察一致。3.2 关键细节空节点必须纳入序列原文档未展开说明的一个实现要点是做序列比较时必须把空节点null也记录进序列。如果不记录空节点下面的反例会直接误判1 / \ 2 2 / / 3 3这棵树左子树是左链2 → 3右子树也是左链2 → 3显然不对称。但若忽略空节点前序遍历1, 2, 3, 2, 3对称前序遍历1, 2, 3, 2, 3两个序列完全相同会被误判为对称一旦把 null 记录进序列结果立即区分开前序遍历1, 2, 3, null, null, null, 2, 3, null, null, null对称前序遍历1, 2, null, 3, null, null, 2, null, 3, null, null序列不同正确判定为不对称。其原理是带 null 标记的前序序列可以唯一确定二叉树的结构对称前序序列又等价于镜像树的普通前序序列所以两个序列相同严格等价于原树等于镜像树即严格等价于对称。因此基于序列比较的解法必须保留空节点标记。3.3 序列比较法代码import java.util.ArrayList; import java.util.List; public class Test { /** * 序列比较法比较前序序列与对称前序序列 * 注意null 必须作为序列元素保留否则结构不对称的树会被误判 */ public static boolean isSymmetricalByTraversal(BinaryTreeNode root) { ListInteger pre new ArrayList(); ListInteger symPre new ArrayList(); preOrder(root, pre); // 前序遍历父 - 左 - 右 symPreOrder(root, symPre); // 对称前序遍历父 - 右 - 左 return pre.equals(symPre); } private static void preOrder(BinaryTreeNode node, ListInteger seq) { if (node null) { seq.add(null); // 空节点也要记录 return; } seq.add(node.val); preOrder(node.left, seq); preOrder(node.right, seq); } private static void symPreOrder(BinaryTreeNode node, ListInteger seq) { if (node null) { seq.add(null); return; } seq.add(node.val); symPreOrder(node.right, seq); // 先右 symPreOrder(node.left, seq); // 再左 } }04 递归解法完整代码与逐层剖析4.1 原文档实例代码完整保留原文档给出的递归解法非常精炼——它把同一棵树当作两个指针从根节点同时出发一个沿left方向走一个沿right方向走逐层成对比较public class Test { private static class BinaryTreeNode { private int val; private BinaryTreeNode left; private BinaryTreeNode right; public BinaryTreeNode() { } public BinaryTreeNode(int val) { this.val val; } Override public String toString() { return val ; } } public static boolean isSymmetrical(BinaryTreeNode root) { return isSymmetrical(root, root); } private static boolean isSymmetrical(BinaryTreeNode left, BinaryTreeNode right) { if (left null right null) { return true; } if (left null || right null) { return false; } if (left.val ! right.val) { return false; } return isSymmetrical(left.left, right.right) isSymmetrical(left.right, right.left); } }4.2 逐层剖析外层入口isSymmetrical(root)调用isSymmetrical(root, root)本质上是把根节点分身成两个游标第一个游标left按从外向内的镜像轨迹移动第二个游标right按对称的镜像轨迹移动。递归函数isSymmetrical(left, right)的三个终止条件顺序很重要条件返回值含义left null right nulltrue两侧同时到底当前位置镜像吻合继续回溯left null \|\| right nullfalse一侧为空另一侧非空结构不对称立即返回失败left.val ! right.valfalse两侧节点值不同值不对称立即返回失败只有三个终止条件都不满足时才继续向下递归且递归组合是交叉配对的isSymmetrical(left.left, right.right)外层与外侧对应左孩子的左 ↔ 右孩子的右isSymmetrical(left.right, right.left)内层与内侧对应左孩子的右 ↔ 右孩子的左。两者用连接任何一侧不成立整体即为不对称。4.3 递归调用轨迹示例以对称树为例跟踪isSymmetrical(root, root)的调用链✓表示该层判定通过isSymmetrical(8, 8) ├── isSymmetrical(6L, 6R) // root.left vs root.right ✓ │ ├── isSymmetrical(5L, 5R) // left.left vs right.right ✓ │ └── isSymmetrical(7L, 7R) // left.right vs right.left ✓ └── isSymmetrical(6R, 6L) // 与上对称实际由交叉递归覆盖对非对称树如某侧多出节点递归会在第一处left null || right null或left.val ! right.val处短路返回false无需遍历整棵树。05 迭代解法队列成对比较递归解法的缺点是依赖系统调用栈树退化成链时栈深为 O(n)。可以用队列把成对比较改写成迭代形式每次从队列取出两个节点按镜像关系配对入队。import java.util.LinkedList; import java.util.Queue; public class Test { /** * 迭代解法利用队列成对比较 * 思路与递归完全一致只是把系统栈换成了显式队列 */ public static boolean isSymmetricalIterative(BinaryTreeNode root) { if (root null) { return true; } QueueBinaryTreeNode queue new LinkedList(); queue.offer(root.left); queue.offer(root.right); while (!queue.isEmpty()) { BinaryTreeNode left queue.poll(); BinaryTreeNode right queue.poll(); if (left null right null) { continue; // 两侧都为空本对通过继续取下一对 } if (left null || right null) { return false; // 一侧为空结构不对称 } if (left.val ! right.val) { return false; // 值不对称 } // 关键按镜像关系成对入队 queue.offer(left.left); // 左子的左 vs 右子的右 queue.offer(right.right); queue.offer(left.right); // 左子的右 vs 右子的左 queue.offer(right.left); } return true; } }入队顺序体现了与递归相同的交叉配对关系(left.left, right.right)与(left.right, right.left)分别作为两对进行比较。由于每次取两个、入队四个队列中的节点数始终是偶数poll取出的必然是一对。06 测试用例与边界验证把递归解法和迭代解法放在同一个可运行的测试类中验证以下为完整可编译代码public class Test { private static class BinaryTreeNode { private int val; private BinaryTreeNode left; private BinaryTreeNode right; public BinaryTreeNode(int val) { this.val val; } } public static boolean isSymmetrical(BinaryTreeNode root) { return isSymmetrical(root, root); } private static boolean isSymmetrical(BinaryTreeNode left, BinaryTreeNode right) { if (left null right null) { return true; } if (left null || right null) { return false; } if (left.val ! right.val) { return false; } return isSymmetrical(left.left, right.right) isSymmetrical(left.right, right.left); } public static void main(String[] args) { // 用例 1空树符合空树对称的约定 System.out.println(isSymmetrical(null)); // true // 用例 2只有一个根节点 System.out.println(isSymmetrical(new BinaryTreeNode(8))); // true // 用例 3对称树 // 8 // / \ // 6 6 // / \ / \ // 5 7 7 5 BinaryTreeNode root new BinaryTreeNode(8); root.left new BinaryTreeNode(6); root.right new BinaryTreeNode(6); root.left.left new BinaryTreeNode(5); root.left.right new BinaryTreeNode(7); root.right.left new BinaryTreeNode(7); root.right.right new BinaryTreeNode(5); System.out.println(isSymmetrical(root)); // true // 用例 4结构对称但值不对称6 换成 9 BinaryTreeNode root2 new BinaryTreeNode(8); root2.left new BinaryTreeNode(6); root2.right new BinaryTreeNode(9); root2.left.left new BinaryTreeNode(5); root2.left.right new BinaryTreeNode(7); root2.right.left new BinaryTreeNode(7); root2.right.right new BinaryTreeNode(5); System.out.println(isSymmetrical(root2)); // false // 用例 5结构不对称两侧都是左链值序列恰好相同 // 1 // / \ // 2 2 // / / // 3 3 BinaryTreeNode root3 new BinaryTreeNode(1); root3.left new BinaryTreeNode(2); root3.right new BinaryTreeNode(2); root3.left.left new BinaryTreeNode(3); root3.right.left new BinaryTreeNode(3); System.out.println(isSymmetrical(root3)); // false } }运行结果true true true false false其中用例 5 正是第 03 节讨论过的忽略空节点会误判的树左右子树都是左链、值序列完全一致但结构并不对称。递归/迭代的成对比较天然处理了空节点因此能正确返回false。07 复杂度分析与延伸思考7.1 复杂度递归解法每个节点至多被比较一次时间复杂度 O(n)其中 n 为节点数空间复杂度取决于树高最坏情况退化为链为 O(n)平均为 O(log n)。迭代解法同样每个节点至多入队一次时间复杂度 O(n)由于队列最多同时容纳一层节点空间复杂度为 O(n)。序列比较法两次遍历各访问每个节点一次时间复杂度 O(n)空间复杂度 O(n)用于存储两个序列。当不对称发生在浅层时递归与迭代解法可以提前短路而序列比较法需要遍历完整棵树。7.2 为什么中序遍历不能用于对称判定如果仿照对称前序遍历定义对称中序遍历右 → 父 → 左会发现它得到的序列恰好是原中序序列的逆序——这是任意二叉树都成立的恒等式无法区分对称与否。前序遍历之所以可行正是因为带 null 标记的前序序列能够唯一确定树的结构这也是二叉树序列化/反序列化的原理参见 leetcode/05.树/10.重建二叉树1.md。7.3 与镜像题的对照对称的二叉树与 leetcode/05.树/22.二叉树的镜像.md 是一对互逆的姊妹题镜像题给定树交换左右子树得到镜像树mirror函数对称题判断原树与自身镜像是否一致。对称题的最优解交叉递归本质上是在不生成镜像的前提下完成原树与镜像逐节点比较而镜像题中的交换操作正好揭示了对称性要求的是左右子树互为镜像这一本质。7.4 典型应用场景判断对称二叉树在工程中常出现在以下场景树形结构的合法性校验如语法分析树、决策树的前后一致性检查二叉树序列化与反序列化后的结构校验面试与算法训练中考察递归思维、镜像配对与边界条件处理的经典题目。相关文档导航原题笔记leetcode/05.树/18.对称的二叉树.md姊妹题镜像leetcode/05.树/22.二叉树的镜像.md二叉树基础leetcode/05.树/00.树的基础介绍.md二叉树定义与性质leetcode/05.树/01.二叉树简介.md二叉树实现与遍历代码leetcode/05.树/02.实现二叉树.md重建二叉树与序列唯一确定性相关leetcode/05.树/10.重建二叉树1.md赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐5分钟掌握uBlock Origin终极浏览器广告拦截与隐私保护指南5分钟掌握uBlock Origin终极浏览器广告拦截与隐私保护指南 还在为网页上无处不在的弹窗广告烦恼吗是否担心自己的浏览行为被悄悄追踪今天我要向你介绍网络安全应用安全游戏机刷 B 站不求人wiliwili 手柄客户端保姆级上手指南游戏机刷 B 站不求人wiliwili 手柄客户端保姆级上手指南 窝在沙发上Switch 横过来左手摇杆翻列表右手按 A 就能开看 B 站——这就是 w音视频桌面应用二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144 本文以 LeetCode 144「二叉树的前序遍历」为核心系统讲解示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
