LeetCode 剑指 Offer 28. 对称的二叉树
题目描述
题意分析
判断二叉树沿根节点的中心线翻转后，节点值和结构是否仍与原树一致。左右对应位置不仅要有相同值，还必须同时存在或同时为空。
对称关系连接的是两个镜像位置，因此递归需要同时拿到两个节点。单独遍历一侧，或者只检查某种遍历结果是否回文，都不能完整判断对应位置的结构。
解法：递归比较
核心思路
[!blue]
定义
isMirror(a,b)表示以a、b为根的两棵子树是否互为镜像。首先处理最小情形：两者都为空，说明对应位置一致；只有一者为空，结构已经不同；两者都非空但值不同，也不能互为镜像。当两者非空且值相同时，镜像会交换左右方向，因此
a.left必须与b.right镜像对应，a.right必须与b.left镜像对应。两组都成立才返回真，用逻辑与连接，任意一组失败就能拒绝整棵树。这些条件正好覆盖镜像的定义：当前根值一致，外侧与内侧的全部结构分别一致。递归每次进入更小的子树，最终到达空节点，便能从边界向上确定所有对应位置是否匹配。
入口调用
isMirror(root,root)，即比较原树与它自身的镜像。两个参数虽然指向同一个根，也不能直接按引用相同判真，仍须继续交叉检查孩子。空树会在“两者都为空”处直接返回真。
解题步骤
- 从
isMirror(root,root)开始。- 若两个节点都为空，返回真；若只有一个为空，返回假，再检查非空节点值是否相同。
- 递归比较
a.left与b.right，以及a.right与b.left。- 返回两次比较的逻辑与。若第一组已经失败，短路求值会停止继续检查第二组。
代码实现
class Solution {
// 对原树调用 isMirror(root, root)。
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private boolean isMirror(TreeNode a, TreeNode b) {
// 对应位置都空才匹配；只有一侧空则结构不同。
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
// 外侧和内侧分别交叉对应，两组必须同时通过。
return isMirror(a.left, b.right) && isMirror(a.right, b.left);
}
}
func isSymmetric(root *TreeNode) bool {
// 对原树调用 isMirror(root, root)。
return isMirror(root, root)
}
func isMirror(a *TreeNode, b *TreeNode) bool {
// 对应位置都空才匹配；只有一侧空则结构不同。
if a == nil && b == nil {
return true
}
if a == nil || b == nil {
return false
}
if a.Val != b.Val {
return false
}
// 外侧和内侧分别交叉对应，两组必须同时通过。
return isMirror(a.Left, b.Right) && isMirror(a.Right, b.Left)
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是节点数。当前入口会按两个方向检查镜像位置，但每个位置只参与常数次比较；提前发现不匹配时可以更早结束。
- 空间复杂度：$O(h)$，其中 $h$ 是树高，递归栈只保留当前一条向下的比较路径，最坏为 $O(n)$。
关键点总结
[!green]
- 镜像比较采用左对右、右对左；若改成同方向比较，判断的就成了两棵树是否完全相同。
- 空节点保留结构信息，必须先判断空，再读取节点值。
- 外侧与内侧是共同要求，不能用其中一组成立代替整棵子树对称。
易错点总结
[!yellow]
- 只比较左右孩子值会漏掉更深层结构差异。
- 用逻辑或会允许一对匹配掩盖另一对失败。
- 只看中序结果是否回文，不能唯一确定树的形状。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 100. 相同的树 | 简单 | 两树相同按左对左、右对右，本题镜像匹配按左对右、右对左。 |
| 226. 翻转二叉树 | 简单 | 交换每个节点的左右子树得到镜像，可用是否与原树相同理解对称性。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！