LeetCode 101. 对称二叉树
目录
题目描述
题意分析
要求判断一棵二叉树是否关于中心竖轴镜像对称，返回布尔值。对称必须同时满足两个方面：形状对称（有孩子的位置一一对应）和取值对称（对应位置的值相等），任何一处不满足就应当返回假。
最容易读错的地方是把「对称」当成「左子树等于右子树」。这两件事不同：对称说的是把右子树整体左右翻转之后才与左子树相同。所以要配对比较的是「左子树的最外侧」和「右子树的最外侧」，也就是左子树往左走的方向对应右子树往右走的方向。
从这个定义能读出配对关系的来源：根节点自己落在轴上，不与任何节点配对；往下每一对配对关系都由「它们的父节点是一对配对节点」决定。这说明判定不是逐节点进行的，而是逐对进行的——这个信号直接决定了判定函数应该接收两个位置而不是一个。
边界情形有四类：两个待比较的位置同时为空，这一侧应当算通过；恰好一个为空而另一个非空，必须立刻判否；单节点树天然对称；节点值可以重复也可以是负数，因此只能靠相等比较来判断，不能依赖取值本身的任何特征。
解法：递归比较镜像节点
核心思路
同时比较一对镜像位置：两个节点都为空时对称，只有一个为空或节点值不同时不对称；其余情况继续交叉比较左树的左孩子与右树的右孩子、左树的右孩子与右树的左孩子。
解题步骤
- 空树直接返回
true。- 从根节点的左右孩子开始成对比较。
- 若一对节点中有空节点，只有两者都为空才对称。
- 节点值相同后，递归比较外侧节点和内侧节点，两组都对称才返回
true。
代码实现
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
if (left == null || right == null) {
return left == right;
}
return left.val == right.val
&& isMirror(left.left, right.right)
&& isMirror(left.right, right.left);
}
}
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
var isMirror func(*TreeNode, *TreeNode) bool
isMirror = func(left, right *TreeNode) bool {
if left == nil || right == nil {
return left == right
}
return left.Val == right.Val &&
isMirror(left.Left, right.Right) &&
isMirror(left.Right, right.Left)
}
return isMirror(root.Left, root.Right)
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点最多比较一次。
- 空间复杂度：$O(h)$，
h为树高，来自递归栈。
关键点总结
- 对称比较的是镜像位置，不是左右子树的同向位置。
- 递归调用必须交叉配对外侧和内侧节点。
- 判空要先于节点值比较。
易错点总结
- 写成
left.left对right.left，实际判断的是两棵树是否相同。- 只判断两个节点都为空，漏掉恰好一个为空的情况。
- 两组递归结果必须用
&&连接。- 仅比较遍历值序列会丢失树的结构信息。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 100. 相同的树 | 简单 | 同为成对递归，但两个子调用同向传参，是理解本题「交叉」二字的最佳对照 |
| 226. 翻转二叉树 | 简单 | 真的交换左右孩子并返回新结构，正是本题靠交叉传参省掉的那一步 |
| 572. 另一棵树的子树 | 简单 | 在「相同判定」外面再套一层「枚举候选根」的遍历，复杂度从线性变成两层嵌套 |
| 951. 翻转等价二叉树 | 中等 | 每一对节点都可以自由选择翻不翻，判定要在同向与交叉两种配对里取或 |
| 剑指 Offer 27. 二叉树的镜像 | 简单 | 要求输出镜像树而不是判断，与 226 题同解，可与本题对照理解「构造」与「判定」之别 |
| 剑指 Offer 28. 对称的二叉树 | 简单 | 与本题同题换皮，适合用来检验三条基准情形与交叉传参能否脱稿写对 |