LeetCode 101：对称二叉树（Symmetric Tree）题解

Symmetric Tree 是 LeetCode Hot 100 里面一道非常经典的二叉树递归题。

这道题看起来很直观： 给定一棵二叉树，判断它是否是轴对称的。

很多人第一次看到这题时，会先从“画图观察”入手，觉得只要左右两边长得一样就行。 但真正写代码时，会发现问题没有那么简单，因为这里的“对称”不是简单地比较：

• 左子树和右子树是不是一样

而是要比较：

左子树的左边，和右子树的右边；左子树的右边，和右子树的左边。

也就是说，它不是“相同”，而是“镜像”。

你给出的这份 Java 代码，使用的是这道题最经典、最标准的一种写法：

递归判断两棵树是否互为镜像

这种写法非常适合这道题，因为“对称”本身就是一个递归定义。 本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给你一棵二叉树的根节点 root，要求你判断这棵树是否是轴对称的。

所谓轴对称，可以简单理解成：

如果把整棵树沿着根节点的中轴线对折，左右两边能够完全重合。

例如下面这棵树：

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

它就是对称的。

而下面这棵树：

        1
      /   \
     2     2
      \     \
       3     3

就不是对称的。

因为左边的 3 在右侧分支，右边的 3 也在右侧分支，两边并没有形成镜像关系。

示例

示例 1

输入：root = [1,2,2,3,4,4,3]
输出：true

因为整棵树左右结构和节点值都完全镜像对称。

示例 2

输入：root = [1,2,2,null,3,null,3]
输出：false

因为虽然左右都有节点值 3，但位置不对称，所以不是镜像结构。

最直接的想法是什么？

如果从最直觉的角度去想，这题的核心其实是：

• 根节点左子树和右子树要互为镜像

• 那么左子树的左孩子应该对应右子树的右孩子

• 左子树的右孩子应该对应右子树的左孩子

于是很自然就能想到一个递归函数：

check(p, q)

表示：

判断以 p 和 q 为根的两棵子树，是否互为镜像。

如果这个函数能写出来，那么整棵树是不是对称，只需要判断：

check(root.left, root.right)

就行了。

这正是你代码的核心思路。

核心思路：把问题转成“两个节点是否镜像”

要判断一棵树是否对称，本质上就是判断它的左右子树是否镜像。

那么对于两个节点 p 和 q，它们什么时候算镜像？

必须同时满足三个条件：

1. 当前节点值相等

p.val == q.val

2. p 的左子树和 q 的右子树镜像

check(p.left, q.right)

3. p 的右子树和 q 的左子树镜像

check(p.right, q.left)

这三个条件同时满足，p 和 q 才能互为镜像。

另外还要注意空节点情况：

• 如果 p 和 q 都为空，说明这一层对称，返回 true

• 如果只有一个为空，另一个不为空，说明结构已经不对称，返回 false

这就是整道题完整的递归逻辑。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

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);
    }
}

代码拆解

这段代码非常简洁，但逻辑非常完整。 下面一步一步来看。

1. 为什么主函数直接比较 root.left 和 root.right？

public boolean isSymmetric(TreeNode root) {
    return check(root.left, root.right);
}

因为整棵树是否对称，本质上取决于：

根节点的左子树和右子树是否互为镜像。

根节点自己不需要比较，因为它就是中轴线所在位置。 真正需要比较的是根节点两侧的结构和数值关系。

所以直接从：

check(root.left, root.right)

开始就可以了。

2. 为什么两个节点都为空时返回 true？

if (p == null && q == null) return true;

因为如果两个位置都没有节点，那么从镜像角度来看，这一层是完全对称的。

例如：

左边没有
右边也没有

这种情况当然不影响整体对称性，所以返回 true。

这是递归中的一个基本边界条件。

3. 为什么只有一个为空时返回 false？

if (p == null || q == null) return false;

因为如果一边有节点，另一边没有节点，那结构就已经不对称了。

例如：

左边有
右边没有

或者：

左边没有
右边有

这两种情况都不可能镜像，所以直接返回 false。

注意这里必须放在访问 p.val 和 q.val 之前，否则会空指针异常。

4. 为什么真正的比较是 p.val == q.val && check(p.left, q.right) && check(p.right, q.left)？

return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);

这是整道题最核心的一句。

对于两个节点 p 和 q，要想它们镜像，必须满足：

当前节点值相同

p.val == q.val

因为如果镜像位置上的值都不一样，那显然不可能对称。

外侧子树镜像

p.left 和 q.right

内侧子树镜像

p.right 和 q.left

注意这里不是：

p.left 和 q.left
p.right 和 q.right

那种写法是在比较“相同”，而不是比较“镜像”。

这一点是整道题最容易写错的地方。

手动模拟一遍

我们用经典对称例子来走一遍：

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

调用：

isSymmetric(root)

会进入：

check(root.left, root.right)

也就是：

check(左边的2, 右边的2)

第一步：比较两个 2

• 两个节点都不为空

• 2 == 2，成立

继续递归比较：

• check(左边2的左孩子3, 右边2的右孩子3)

• check(左边2的右孩子4, 右边2的左孩子4)

第二步：比较两个 3

• 两个节点都不为空

• 3 == 3

再继续递归：

• check(null, null) -> true

• check(null, null) -> true

所以这一层成立。

第三步：比较两个 4

同理：

• 4 == 4

• 左右子树都是空，对称

这一层也成立。

最终结果

三部分都成立，所以整棵树对称，返回：

true

再看一个不对称的例子

例如：

        1
      /   \
     2     2
      \     \
       3     3

调用：

check(root.left, root.right)

先比较两个 2，值相等，继续递归：

• check(p.left, q.right)：也就是 check(null, 3) -> false

• check(p.right, q.left)：也就是 check(3, null) -> false

只要有一个分支不满足，整体就不是镜像。

所以最终返回：

false

这也正好符合题意。

为什么这个方法是正确的？

因为“镜像”的定义本身就是递归的。

对于两个节点 p 和 q 来说，它们镜像，当且仅当：

1. 当前节点值相等

2. p.left 和 q.right 镜像

3. p.right 和 q.left 镜像

而你的递归函数 check(p, q) 做的事情，恰好就是把这个定义完整地翻译成代码。

另外，边界条件也处理得很清楚：

• 都为空 -> 对称

• 一个为空 -> 不对称

所以这个递归过程与“镜像”的数学定义完全一致，因此是正确的。

复杂度分析

假设二叉树一共有 n 个节点。

时间复杂度

每个节点最多会被访问一次，所以时间复杂度是：

O(n)

空间复杂度

额外空间主要来自递归调用栈。

最坏情况下，如果树退化成链表，递归深度会达到 n，所以空间复杂度是：

O(n)

如果树比较平衡，那么递归深度大约是树高：

O(log n)

但通常按最坏情况写 O(n)。

这道题真正想考什么？

这道题表面上是在判断树是否对称，但本质上考察的是二叉树递归中“两个节点关系”的处理能力。

第一，是否能把“整棵树是否对称”转化成“两个子树是否镜像”

很多树题的关键，都在于把一个全局问题转成递归子问题。 这题最核心的转化就是：

整棵树对称 <=> 左右子树镜像

第二，是否能区分“相同”和“镜像”的区别

这是这题最容易写错的地方。

• 比较相同：左对左，右对右

• 比较镜像：左对右，右对左

如果这一步没想清楚，代码就很容易写偏。

第三，是否能熟练处理空节点边界

树递归题里，空节点判断几乎是必修课。 这题里两个空节点返回 true、一个空节点返回 false，就是最典型的边界处理。

这题还有别的写法吗？

有。

除了递归写法之外，这题也可以用：

队列 / 迭代法

来做。

做法通常是：

• 每次成对取出两个节点

• 比较它们是否镜像

• 再把对应需要比较的子节点成对放入队列

不过从理解角度来说，递归写法是最自然的，因为它最贴合“镜像”的定义。

和“相同的树”有什么区别？

这两题很适合放在一起对比。

相同的树

判断两棵树是否完全相同：

• 当前值相同

• 左对左

• 右对右

对称二叉树

判断一棵树左右是否镜像：

• 当前值相同

• 左对右

• 右对左

所以这两题的结构很像，但比较方向不同。 理解这一点之后，这题就会清晰很多。

总结

这道题的核心思想可以概括成一句话：

判断一棵树是否对称，本质上就是递归判断它的左右子树是否互为镜像。

具体做法就是：

1. 从根节点的左子树和右子树开始比较

2. 如果两个节点都为空，说明当前对称

3. 如果只有一个为空，说明不对称

4. 如果两个节点值不同，也不对称

5. 否则继续递归比较：

   • 左节点的左子树 和 右节点的右子树

   • 左节点的右子树 和 右节点的左子树

只有这两部分都成立，当前两棵子树才互为镜像。

这是一道非常经典、也非常值得认真理解的二叉树递归题。 因为它会让你真正体会到：

• 递归定义如何直接翻译成代码

• “镜像关系”在树里该怎么表达

• 同样是树比较题，比较方向不同，问题本质就完全不同

把这道题真正吃透之后，再去看：

• 相同的树

• 翻转二叉树

• 最大深度

• 路径总和

这些二叉树基础题时，你会更容易写出清晰的递归结构。

因为“对称二叉树”本身就是二叉树递归题里非常经典的一道模板题。