对称二叉树 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你一个二叉树的根节点 root，检查它是否轴对称。

轴对称指：以根为轴，左子树与右子树互为镜像——对应位置的节点值相等，且子结构也镜像对应。

节点数目在 [1, 1000]，节点值在 [-100, 100] 范围内。

示例 1

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

输出：true

示例 2

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

输出：false

左子树的右孩子为 3，右子树的左孩子为 3，但它们不是镜像位置上的对应节点（一侧缺左孩子、另一侧缺右孩子）。

💭 模拟答题者思考

1. 暴力直觉：把树按层序列化再判断字符串是否回文——要编码空指针且层序与「镜像」定义不完全一致，实现啰嗦。

2. 重复在哪里？「是否对称」在根处等价于：左、右子树是否互为镜像；而「两子树是否镜像」在每一对对齐节点上又是同一类问题——子问题同型，适合递归。

3. 与「相同的树」对比：相同树是 (p.left,q.left) 与 (p.right,q.right)；镜像则是 (a.left,b.right) 与 (a.right,b.left)，内外交叉配对。

4. 示例 2：[1,2,2,null,3,null,3] 在比较 (2,null) 与 (2,3) 时一空一非空，直接假。

5. 单节点树 [1] 无左右孩子，isSymmetric 在检查 root.left 与 root.right 双空时即真；总时间 O(n)，空间 O(h)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`left` / `right`	TreeNode*	定义：当前正在做「镜像对齐」的一对节点，初始为 `root.left` 与 `root.right` 维护：若两者都空则该对子树镜像成立；仅一方空则整棵树不对称；值不等则假更新：下一对为 `(left.left, right.right)` 与 `(left.right, right.left)`——外对内、内对外
`mirror(a,b)`	bool	定义：以 `a`、`b` 为根的子树是否互为镜像维护：真当且仅当当前值相等，且 `a` 的左与 `b` 的右镜像、`a` 的右与 `b` 的左镜像更新：`return mirror(a.left,b.right) and mirror(a.right,b.left)`

⌨️ 落码步骤

1. 若 root 为空，返回 true（题目 n≥1 时通常可省略）

2. 定义 mirror(a,b)：双空 → true；一空一非空或 a.val != b.val → false

3. 返回 mirror(a.left,b.right) and mirror(a.right,b.left)

4. isSymmetric(root) 调用 mirror(root.left, root.right)

5. （迭代备选）队列成对入队 (left,right)，弹出后按镜像规则把孩子成对入队

💻 代码实现

class Solution:
    def isSymmetric(self, root: TreeNode | None) -> bool:
        def mirror(a: TreeNode | None, b: TreeNode | None) -> bool:
            if not a and not b:
                return True
            if not a or not b or a.val != b.val:
                return False
            return mirror(a.left, b.right) and mirror(a.right, b.left)

        if not root:
            return True
        return mirror(root.left, root.right)

# 迭代（队列存镜像对）：
# from collections import deque
# def isSymmetric(self, root):
#     if not root: return True
#     q = deque([(root.left, root.right)])
#     while q:
#         a, b = q.popleft()
#         if not a and not b: continue
#         if not a or not b or a.val != b.val: return False
#         q.append((a.left, b.right))
#         q.append((a.right, b.left))
#     return True

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return mirror(root->left, root->right);
    }
    bool mirror(TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;
        if (!a || !b || a->val != b->val) return false;
        return mirror(a->left, b->right) && mirror(a->right, b->left);
    }
};
// 时间 O(n)，空间 O(h)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(h)（递归栈，h 为树高；BFS 队列同理）

⚠️ 常见坑

❗ 误用「相同树」配对：写成 mirror(a.left,b.left) 会把「结构对称」当成「两棵相同子树」，示例 1 仍可能对，但镜像定义错误。

❗ 只比较根左右值相等就返回 true：必须递归检查整棵左右子树是否镜像。

❗ BFS 入队顺序错：第二对必须是 (a.left,b.right) 与 (a.right,b.left)，不能两对都按同侧孩子入队。

🔍 必测边界 Case

Case 1：单节点

root = [1] → true

Case 2：官方示例 1（完全对称）

root = [1,2,2,3,4,4,3] → true

Case 3：官方示例 2（缺一侧孩子）

root = [1,2,2,null,3,null,3] → false

Case 4：根左右值不等

root = [1,2,3] → false