CS-Notes 剑指 Offer 题解：对称的二叉树——用递归对比双树判定镜像对称

本篇围绕 CS-Notes 仓库中剑指 Offer 第 28 题「对称的二叉树」的题解展开，完整继承原文档的题目描述与 Java 递归解法，并在此基础上补充判定逻辑的逐行剖析、时间/空间复杂度推导、非递归（队列/栈）实现、边界陷阱以及同仓库内「二叉树镜像」「LeetCode 101 树的对称」等关联题解的印证。读完本文，你将掌握二叉树镜像对称问题的核心建模方法——把"单树自对称"转化为"两棵树互为镜像"的递归对比，并能写出面试白板可直接默写的两种解法。

题目描述

题目出自《剑指 Offer》第 28 题（原文档给出的在线练习入口为牛客网剑指 Offer 专题，可在刷题网站中搜索原题）。原题描述如下：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

题目所配示意图（上方图片）直观展示了"对称"的含义：左边那棵树 1 → (2, 3) 与右边那棵树 1 → (3, 2) 互为镜像——以根节点为轴，左子树整体翻折后与右子树完全重合。该图在仓库中同时被 27. 二叉树的镜像 一题引用，两题共享同一组图形素材，也印证了"镜像"与"对称"在概念上的紧密联系：一棵树对称，等价于它与自己的镜像相同。

在剑指 Offer 题解体系中，本题归属于「树」这一章节，完整题目索引可参考 剑指 Offer 题解 - 目录。

核心建模：把单树问题转化为双树对比

判定一棵树是否对称，最直接的直觉是"从左到右看"与"从右到左看"是否一致。但更有效的方法是把问题拆成两个节点的配对比较：

• 根节点自己和自己比，天然相等，因此判定入口是「比较根节点的左子树与右子树」；
• 对于任意一对需要比较的节点 (t1, t2)（它们本应互为镜像位置），需要同时满足三个条件：
  1. 要么两个都为空（都为空是"匹配"，一个空一个不空则不对称）；
  2. 值相等：t1.val == t2.val；
  3. 交叉递归成立：t1 的左子节点要与 t2 的右子节点比，t1 的右子节点要与 t2 的左子节点比。

注意第 3 条中的交叉方向（左对右、右对左）——这正是"镜像"区别于"两棵树相同"的关键。如果是判断两棵树是否完全相同（如同仓库 26. 树的子结构 中的 isSubtreeWithRoot，比较的是 left 对 left、right 对 right），方向是同向的；而对称判定必须是交叉的。

递归解法（原文档实现）

原文档给出的 Java 解法是标准的递归实现，完整代码如下（与原文档保持一致）：

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null)
        return true;
    return isSymmetrical(pRoot.left, pRoot.right);
}

boolean isSymmetrical(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null)
        return true;
    if (t1 == null || t2 == null)
        return false;
    if (t1.val != t2.val)
        return false;
    return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left);
}

逐行剖析其设计：

1. 入口函数 isSymmetrical(TreeNode pRoot) 处理了两个全局边界：

   • 空树（pRoot == null）返回 true。空树没有不对称的可能，这是很多候选者容易漏掉的约定，也是牛客网测试用例中常见的边界输入；
   • 非空树则把问题转化为「比较 pRoot.left 与 pRoot.right 这一对节点」，根节点的值不需要比较（它自己和自己比必然相等）。

2. 两节点版本 isSymmetrical(TreeNode t1, TreeNode t2) 是递归主体，判空顺序值得留意：

   • t1 == null && t2 == null 先判断，返回 true——两空配对是合法的终止情形；
   • 紧接着 t1 == null || t2 == null 返回 false——一空一不空，结构就不对称了。如果把这两个条件顺序写反（例如先写 t1 == null || t2 == null），两个都为空时会错误地返回 false，导致"两节点都没有子树"的叶子配对全部误判。这是本题最典型的笔误；
   • t1.val != t2.val 返回 false，值先比较可以尽早剪枝；
   • 最后一行 isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left) 完成交叉递归，且利用 && 的短路特性：前半部分不对称时不再计算后半部分。

这个双参递归签名（isSymmetric(t1, t2)）是二叉树镜像类问题的通用模板。同仓库 Leetcode 题解 - 树 中「9. 树的对称」（LeetCode 101. Symmetric Tree）使用的正是同构代码，仅方法名与参数命名不同，可以对照阅读验证这一模板的通用性。

复杂度分析

• 时间复杂度 O(n)：每个节点恰好参与一次配对比较（对称性成立时左右子树节点一一配对；不对称时提前剪枝，实际比较更少），n 为节点总数。
• 空间复杂度 O(h)：h 为树高，即递归调用栈的最大深度。最坏情形（退化为链表）为 O(n)；平衡树为 O(log n)。

以示意图中的小树为例走一遍：入口比较 (left=2, right=3) → 值 2 != 3 直接返回 false，全树只需 1 次节点比较即得出结论，体现了"值比较前置剪枝"的价值。

非递归解法：用栈或队列显式保存节点对

如果面试时要求"不使用递归"（或树非常深、担心栈溢出），可以把上述递归改写为显式的栈/队列版本，本质是"按层处理节点对"：

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null)
        return true;
    Deque<TreeNode[]> stack = new ArrayDeque<>();
    stack.push(new TreeNode[] { pRoot.left, pRoot.right });
    while (!stack.isEmpty()) {
        TreeNode[] pair = stack.pop();
        TreeNode t1 = pair[0], t2 = pair[1];
        if (t1 == null && t2 == null)
            continue;
        if (t1 == null || t2 == null)
            return false;
        if (t1.val != t2.val)
            return false;
        // 与递归版保持同样的交叉顺序
        stack.push(new TreeNode[] { t1.left, t2.right });
        stack.push(new TreeNode[] { t1.right, t2.left });
    }
    return true;
}

要点说明：

• 判空与判值的逻辑与递归版逐条对应（两空跳过、一空一不空判 false、值不等判 false），仅把隐式调用栈换成了显式 Deque；
• 每轮弹出的一对节点是"本应互为镜像"的两个位置，因此入栈的两个新配对同样是交叉的：(t1.left, t2.right) 与 (t1.right, t2.left)；
• 若改用 Queue（BFS 风格）做层次遍历，复杂度结论不变，空间上限仍受同一层节点对数量约束，约为 O(n)（最坏一层放满时）。

边界与易错点小结

结合仓库中原文档代码与同类题解，列出面试与自测时最容易踩的坑：

1. 空根返回 true：pRoot == null 必须显式返回 true，否则空树输入直接出错；
2. 判空顺序：t1 == null && t2 == null 必须在 t1 == null || t2 == null 之前判断，原因如前所述；
3. 比较方向不能写直：必须是 t1.left ↔ t2.right、t1.right ↔ t2.left 的交叉配对。写成 t1.left ↔ t2.left 变成的是"判断两棵子树是否相同"，对 1 → (2, 3) / 1 → (3, 2) 这类镜像树会判错；
4. 只比较值不够：结构不同（一边有节点一边为空）时值比较永远不会执行，必须先处理结构不一致；
5. 单节点树：pRoot 只有根、无左右子节点时，入口传入 (null, null)，第一分支即返回 true，逻辑自洽。

与仓库内相关题解的关联

本题在 CS-Notes 的剑指 Offer 体系中有几个天然的前后呼应，建议按以下线索串起来复习：

• 27. 二叉树的镜像：给定一棵树，递归交换每个节点的左右子节点生成其镜像。理解了"镜像"的构造，就理解了第 28 题的判定标准——一棵对称的树，其镜像与自身相同；本题的递归判定其实就是"构造镜像"过程的无副作用（只比较、不修改）版本，二者共享同一幅示意图；
• 26. 树的子结构：其 isSubtreeWithRoot 同样是双参递归，但比较方向是同向的（left-left、right-right）。两题放在一起对比，能清晰区分"树相同"与"树互为镜像"两种递归模板；
• Leetcode 题解 - 树 中「9. 树的对称」（LeetCode 101）：与本题思路完全一致的双参递归实现，可作为跨题库的同构印证。

小结

判断二叉树是否对称的关键，是把"一棵树自己对称"重写为"它的左、右子树互为镜像"，然后用 isSymmetrical(t1, t2) 这一交叉递归模板完成配对比较；判空顺序、交叉方向、空树约定是三个最容易出错的细节。递归版代码短、易默写，是面试首选；显式栈/队列版则覆盖了非递归要求与深树场景。两者复杂度均为时间 O(n)、空间 O(h)，可直接应用于剑指 Offer 第 28 题及 LeetCode 101 的判定需求。