知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 对称二叉树 ## 题目(LeetCode 101) 判断一棵二叉树是否是镜像对称的。 ``` 对称 ✓ 不对称 ✗ 1 1 / \ / \ 2 2 2 2 / \ / \ \ \ 3 4 4 3 3 3 ``` ## 大白话理解 把树从中间劈开,左半边和右半边是不是镜像? 不是拿整棵树和自己比,而是拿左子树和右子树比。比较的规则是: - 左子树的左孩子 vs 右子树的右孩子(外侧) - 左子树的右孩子 vs 右子树的左孩子(内侧) ``` 1 / \ 2 2 ← 2 == 2 ✓ / \ / \ 3 4 4 3 ← 外侧:3 vs 3 ✓ 内侧:4 vs 4 ✓ ``` 想象两个人面对面站着(镜像),你的左手对应我的右手,你的右手对应我的左手。 ## 代码 ```java 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; // 值不相等 → 不对称 if (left.val != right.val) return false; // 外侧比较 + 内侧比较 return isMirror(left.left, right.right) // 外侧 && isMirror(left.right, right.left); // 内侧 } ``` ### 逐行拆解 ``` isMirror(left, right) 的含义:left 和 right 这两棵子树是否互为镜像 终止条件: 都是 null → 对称,返回 true 一个 null 一个不是 → 不对称,返回 false 值不相等 → 不对称,返回 false 递归: left 的左孩子 和 right 的右孩子 要镜像(外侧) left 的右孩子 和 right 的左孩子 要镜像(内侧) 两个条件都满足才是对称的 ``` ## 画图模拟 ``` isSymmetric(1) → isMirror(2, 2) 值相等 ✓ → isMirror(3, 3) 外侧 值相等 ✓ → isMirror(null, null) ✓ → isMirror(null, null) ✓ 返回 true → isMirror(4, 4) 内侧 值相等 ✓ → isMirror(null, null) ✓ → isMirror(null, null) ✓ 返回 true 返回 true && true = true ``` ## BFS 写法 ```java public boolean isSymmetric(TreeNode root) { if (root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root.left); queue.offer(root.right); while (!queue.isEmpty()) { TreeNode left = queue.poll(); TreeNode 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); queue.offer(right.right); queue.offer(left.right); queue.offer(right.left); } return true; } ``` ## 复杂度 - 时间:O(n) - 空间:O(h) ## 一句话总结 两个指针一左一右,外侧对外侧,内侧对内侧,递归比较。 --- 上一篇:[03 - 翻转二叉树](./03-invert-tree.md) | 下一篇:[05 - 二叉树的直径](./05-diameter.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入