LeetCode 101. 对称二叉树
题目描述
题意分析
判断二叉树是否关于根节点左右镜像对称。对应位置不但要有相同的节点值，还必须同时存在或同时为空；仅比较两边包含哪些值，无法判断结构是否对称。
镜像会交换左右方向：左子树的左孩子对应右子树的右孩子，左子树的右孩子对应右子树的左孩子。整棵树是否对称，等价于根节点的左右子树是否互为镜像。题目进阶要求分别给出递归和迭代写法，两者都需要成对检查镜像位置。
解法：递归比较镜像节点
核心思路
[!blue]
定义
isMirror(left, right)判断以这两个节点为根的子树是否互为镜像。它处理的是一对位置，因此每次递归都必须同时传入左右两边的对应节点，不能分别判断每棵子树自身是否对称。先处理空节点：两者都为空，说明这个位置的结构一致，返回
true；只有一个为空，说明另一侧多出节点，返回false。都非空时才比较节点值，值不同也立即失败。如果当前值相同，还需要同时满足两组镜像关系：外侧的
left.left与right.right互为镜像，内侧的left.right与right.left互为镜像。这两组覆盖了两个当前节点下面的全部位置，因此用逻辑与连接它们；任意一组不对称，整个子树就不对称。每次递归都转向更小的子树，最终会到达空节点。若所有对应位置的结构和值都匹配，就逐层返回
true；只要有一处不匹配，false就会传回根部。空树无需比较，直接视为对称。
解题步骤
- 根节点为空时返回
true，否则调用isMirror(root.left, root.right)。- 如果一对节点中存在空节点，返回它们是否都为空。
- 两个节点都非空时，比较节点值；不同则返回
false。- 递归检查外侧和内侧两对节点，只有两组都返回
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为树高，来自递归栈。
关键点总结
[!green]
- 对称比较的是镜像位置，不是左右子树的同向位置。
- 递归调用必须交叉配对外侧和内侧节点。
- 判空要先于节点值比较。
解法二：队列迭代比较镜像节点
核心思路
[!blue]
递归中每次等待处理的任务都是“一对镜像位置”，因此也可以把这些节点对显式放进队列。队列最初保存根节点的左右孩子，每次取出一对，按照与递归完全相同的规则检查。
两个节点都为空时，这一对已经匹配，继续处理下一对；只有一个为空或节点值不同，立即返回
false。两者非空且值相等时，把外侧一对、内侧一对加入队列，等待后续检查。只有队列处理完且没有发现冲突，才返回true。空节点也要保留在节点对中，因为它们表示结构中缺失的位置，不能先过滤掉再只比较非空节点。Java 的
ArrayDeque不允许直接放入空元素，所以队列保存的是非空的二元素数组，数组内的两个节点可以为空；Go 同样使用二元素数组表示一对节点。这个过程只是用队列替代了递归调用栈，镜像配对关系没有变化。每个子节点只会由对应的父节点对加入一次，因此所有镜像位置都会被检查，也不会重复扩展。
解题步骤
- 空树返回
true，否则把根节点的左右孩子作为一对入队。- 取出一对节点；若都为空，跳过这一对。
- 若只有一个为空，或两者值不同，返回
false。- 将外侧
(left.left, right.right)和内侧(left.right, right.left)分别作为一对入队。- 重复到队列为空，返回
true。
代码实现
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode[]> queue = new ArrayDeque<>();
queue.offer(new TreeNode[] {
root.left,
root.right
});
while (!queue.isEmpty()) {
TreeNode[] pair = queue.poll();
TreeNode left = pair[0];
TreeNode right = pair[1];
if (left == null && right == null) {
continue;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
queue.offer(new TreeNode[] {
left.left,
right.right
});
queue.offer(new TreeNode[] {
left.right,
right.left
});
}
return true;
}
}
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
queue := [][2]*TreeNode{
{
root.Left,
root.Right,
},
}
for len(queue) > 0 {
pair := queue[0]
queue = queue[1:]
left, right := pair[0], pair[1]
if left == nil && right == nil {
continue
}
if left == nil || right == nil || left.Val != right.Val {
return false
}
queue = append(queue, [2]*TreeNode{
left.Left,
right.Right,
}, [2]*TreeNode{
left.Right,
right.Left,
})
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点最多参与一对比较，空位置的检查次数同样为线性量级。
- 空间复杂度：$O(w)$，
w为树的最大层宽，队列保存等待比较的节点对，最坏为 $O(n)$。
关键点总结
[!green]
- 任务必须成对入队：每一项都明确表示应该互为镜像的两个位置。
- 空位置参与比较：只有两者都为空才可以跳过，不能只把非空孩子入队。
- 先判空再读值：这样既避免空指针，也能立即发现结构不一致。
易错点总结
[!yellow]
- 写成
left.left对right.left，实际判断的是两棵树是否相同。- 只判断两个节点都为空，漏掉恰好一个为空的情况。
- 两组递归结果必须用
&&连接。- 仅比较遍历值序列会丢失树的结构信息。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 100. 相同的树 | 简单 | 两树相同按左对左、右对右，本题镜像匹配按左对右、右对左。 |
| 226. 翻转二叉树 | 简单 | 交换每个节点的左右子树得到镜像，可用是否与原树相同理解对称性。 |
| 572. 另一棵树的子树 | 简单 | 递归比较对应节点及两侧子树；本题比较左右镜像位置，该题在大树各位置寻找相同子树。 |