021 · Symmetric Tree

algorithm

Published

May 26, 2026

My First Thoughts

看到这道题，第一反应可能是：

逐个递归比较，看每一层是否镜像。如果是，就继续递进；如果不是，就提前返回 False。

这个方向是对的。

因为对称二叉树不是只要求左右节点值一样，还要求左右两边的结构像镜子一样对应。

比如这棵树是对称的：

第一层只有 root，它自己当然是对称中心。真正要比较的是：

root.left  和 root.right

如果这两个节点的值相同，第一步看起来就通过了。

但继续往下时，就会遇到这题最容易卡住的地方：

root.left.left

它不是和 root.left.right 比较，而是要和另一边的镜像位置比较：

root.left.left   <-> root.right.right
root.left.right  <-> root.right.left

也就是说，我们比较的不是“同一棵子树内部的左右”，而是“左子树和右子树之间的镜像位置”。

Why That Is Not Enough

如果只写一个递归函数，参数是单个 root，会很难表达这个关系。

因为在某一层里，我们需要同时知道两个节点：

左边的某个节点
右边与它镜像对应的节点

只拿一个 root 时，代码容易变成：

root.left == root.right

但这并不够。

一方面，root.left == root.right 比较的可能是对象本身，不是我们真正想要的“值相同、结构镜像”。

另一方面，即使当前这一对节点值相同，下一层也不是普通的：

left.left  <-> right.left
left.right <-> right.right

而是镜像比较：

left.left  <-> right.right
left.right <-> right.left

所以这道题的关键不是“怎么一层一层扫”，而是把递归函数设计成：一次比较两个镜像位置上的节点。

Final Idea

定义一个辅助函数：

isMirror(left, right) 返回以 left 和 right 为根节点的两棵子树是否互为镜像。

这样问题就变清楚了。

先处理空节点：

if left is None and right is None:
    return True

两个位置都没有节点，说明这一部分是对称的。

再处理只有一个为空的情况：

if left is None or right is None:
    return False

一边有节点，另一边没有节点，结构已经不对称了。

接着比较当前两个节点的值：

if left.val != right.val:
    return False

如果当前镜像位置上的值不同，也不是对称树。

最后继续比较下一层的镜像位置：

return isMirror(left.left, right.right) and isMirror(left.right, right.left)

这句话就是整道题的核心。

普通的相同树比较是：

left.left  <-> right.left
left.right <-> right.right

而对称树比较是：

left.left  <-> right.right
left.right <-> right.left

主函数只需要从根节点的左右子树开始：

return isMirror(root.left, root.right)

如果 root 本身是空树，直接返回 True。

以这棵树为例：

递归关系可以这样看：

isMirror(2, 2)
├── isMirror(3, 3) → True
└── isMirror(4, 4) → True

=> True and True
=> True

如果是这棵树：

递归时会遇到：

isMirror(None, 3) → False

所以整棵树不是对称的。

Why It Works

对称二叉树的判断，本质上是一个递归条件：

当前两个镜像节点的值相同
左边节点的左子树 和 右边节点的右子树 互为镜像
左边节点的右子树 和 右边节点的左子树 互为镜像

递归函数 isMirror(left, right) 的含义很明确：判断 left 和 right 这两棵子树是否互为镜像。

对于任意一对镜像位置上的节点：

两个都为空，说明这一部分对称
只有一个为空，说明结构不对称
两个都不为空，但值不同，说明内容不对称
当前节点值相同，就继续交叉比较下一层

因为每一对镜像位置都按同样规则检查，而且两边递归结果都必须是 True，所以只有整棵树结构和值都镜像对应时，最终才会返回 True。

Code

def isSymmetric(root):
    if root is None:
        return True

    def isMirror(left, right):
        if left is None and right is None:
            return True

        if left is None or right is None:
            return False

        if left.val != right.val:
            return False

        return isMirror(left.left, right.right) and isMirror(left.right, right.left)

    return isMirror(root.left, root.right)

Complexity

Time	\(O(n)\) — 每个节点最多被访问一次
Space	\(O(h)\) — 递归调用栈的深度等于树的高度 `h`，最坏情况下（树退化成一条链）是 \(O(n)\)

Takeaway

判断对称树时，不要只拿一个 root 在内部比较左右。更清楚的递归定义是：一次拿两个镜像位置上的节点，判断它们是否互为镜像。核心关系是 left.left 对 right.right，left.right 对 right.left。

← Quiz