#101
简单
中频
递归法对称二叉树
这是一道围绕树、二叉树、递归展开的高频练习。建议先掌握「递归法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
递归
题目分析
这道题表面上是在处理「对称二叉树」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 树、二叉树 这些能力。这类题更像在一棵决策树里向下展开，关键是递归时带什么状态、什么时候回退。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：递归同时比较左子树的左/右分支和右子树的右/左分支，判断它们是否镜像对称。
推荐代码
推荐解法：递归法
时间复杂度： O(n)
空间复杂度： O(h)
核心思路： 递归同时比较左子树的左/右分支和右子树的右/左分支，判断它们是否镜像对称。
// 二叉树节点定义
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}结构化讲解
面试时怎么讲
开场思路
这题我会把它写成“判断两棵树是否镜像”的递归。
核心过程
- 先比较当前这两个节点是否都为空、是否值相等。
- 当前层合法后，再递归比较外侧一对节点。
- 同时递归比较内侧一对节点。
- 只有两组都成立，整体才对称。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(h)。
面试补一句：这题最值得强调的是“镜像比较一定是交叉递归”。
核心思路
对称树不是比较同侧，而是比较镜像位置。每一对节点都要同时满足值相等，并且它们的外侧和内侧子树也分别镜像。
步骤讲解
1
把问题变成比较两棵树是否镜像
递归函数接收两个节点，判断它们为根的子树是否互为镜像。
为什么这样做：原问题正好可以拆成“左子树是否和右子树镜像”。
对应代码提示：return isMirror(root.left, root.right);
2
先处理空节点和数值判断
两个节点都空则对称；一个空一个不空或值不同则不对称。
为什么这样做：镜像比较必须先在当前层判定是否成立。
对应代码提示：if (left == null || right == null) return left == right;
3
递归比较外侧和内侧
继续比较 left.left 对 right.right，以及 left.right 对 right.left。
为什么这样做：镜像关系体现在交叉位置，而不是同方向位置。
对应代码提示：return isMirror(left.left, right.right) && isMirror(left.right, right.left);
易错点
递归比较了同侧孩子
那是在判断相同结构，不是镜像结构。
正确理解：必须交叉比较外侧和内侧节点。
只比较节点值不比较结构
值一样但结构不同的树仍然不对称。
正确理解：空节点组合和递归结构都要一起比较。
把空节点处理混掉
镜像判断里空节点是非常关键的结构信息。
正确理解：两个都空才算对称，一个空一个不空立刻 false。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(h)
比其他方案更好在哪里：比迭代队列法更短，更容易从定义直接推出来。
适用判断：树题若条件本身就是镜像、对称、对应关系，优先考虑双节点递归。
额外提醒
- 对称判断的关键词不是“相同”，而是“镜像”。
其他语言 / 其他解法
迭代法
算法思路待补充
迭代法
算法思路待补充
时间复杂度：O(n)
空间复杂度：O(n)
一句话思路：算法思路待补充
// 二叉树节点定义
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode u, TreeNode v) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(u);
q.offer(v);
while (!q.isEmpty()) {
u = q.poll();
v = q.poll();
if (u == null && v == null) {
continue;
}
if ((u == null || v == null) || (u.val != v.val)) {
return false;
}
q.offer(u.left);
q.offer(v.right);
q.offer(u.right);
q.offer(v.left);
}
return true;
}
}动画演示
如果你还没完全看懂，可以展开动画演示。
递归法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
递归法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树的数组表示（用逗号分隔），然后点击开始
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树的数组表示（用逗号分隔），然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。