LeetCode 剑指 Offer 28. 对称的二叉树

2021-06-10 HGNULB 约 9 分钟

文章信息 9 个分类 4 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动阿里巴巴剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 28. 对称的二叉树

题意分析

判断一棵二叉树是不是「关于根节点左右对称」的，也就是把它沿着穿过根的竖直中轴线折叠后，左右两半能完全重合。

「重合」既要求结构对称，也要求对应位置的节点值相等。缺一不可：[1,2,2] 结构对称且值相等，返回真；[1,2,3] 结构对称但值不同，返回假；[1,2,2,null,3,null,3] 值看起来配得上，但两个 3 都挂在各自父节点的右边，折叠后对不上，返回假。第三个例子是本题最经典的反例，读题时就该先想到它。

关键要看清对称是跨子树的成对比较，而不是每棵子树各自的性质。判断根的左子树是否对称、右子树是否对称，跟整棵树是否对称没有直接关系——真正要比的是「左子树」和「右子树」这一对是否互为镜像。这一点决定了递归函数必须接收两个节点参数，而题目给的 isSymmetric 只有一个，所以一定要另开一个辅助函数。这是本题的核心设计。

「互为镜像」展开来说是：两个节点的值相等，并且 A 的左孩子与 B 的右孩子互为镜像、A 的右孩子与 B 的左孩子互为镜像。注意是交叉配对，不是同侧配对——这是全题唯一的技术点。

节点数上限是 1000，$O(n)$ 遍历毫无压力，递归深度最坏 1000 层也在安全范围内。

边界：空树按定义是对称的，返回真；单节点树也对称。这两种都应该自然落进递归基，不需要额外分支。

解法：递归比较

核心思路

一个诱人的错误起点是「中序遍历后判断结果是不是回文串」。它在很多用例上碰巧成立，但会在 [1,2,2,2,null,2] 这类含重复值的树上失效——遍历序列相同的树未必同构，把结构信息压成一维序列就丢掉了空节点的位置。要修补它就得在遍历时给空节点也输出占位符，那还不如直接比结构。

回到结构本身。瓶颈在于 isSymmetric(root) 的签名只有一个参数，而对称性描述的是两个子树之间的关系，单参数递归无法表达。

于是把问题重新表述：定义辅助函数 isMirror(a, b)，回答「以 a 为根的树与以 b 为根的树是否互为镜像」。有了它，原问题就是 isMirror(root.left, root.right)——或者更省事地写成 isMirror(root, root)，让第一层递归自动展开成对左右孩子的交叉比较，同时把 root == null 的情形也一并吞掉，无需任何特判。

isMirror 的递归结构直接来自镜像的定义：两棵树互为镜像，当且仅当根值相等，且 A 的左与 B 的右互为镜像、A 的右与 B 的左互为镜像。交叉配对正是「镜像」二字在代码里的体现，写成同侧配对得到的是「两棵树相同」，那是另一道题（100. 相同的树）。

递归基有三条，顺序不能乱。先判「两者同时为空」返回真——两棵空树当然互为镜像。再判「其中恰好一个为空」返回假——一边有节点一边没有，结构不可能对称。这两条必须按此顺序：如果先写 a == null || b == null 就会把「都为空」的合法情形也判成假。最后判值不等返回假。走过这三关之后 a 和 b 都非空且值相等，可以安全访问它们的孩子。

用短路与 && 连接两个递归调用，任何一侧发现不对称就立即停止，不再展开另一侧——这对提前失败的用例是实打实的剪枝。

解题步骤

主函数直接返回 isMirror(root, root)：把同一棵树当作两个参数传入，第一层递归会展开成 isMirror(root.left, root.right) 与 isMirror(root.right, root.left)，两者互为对偶、结论一致。这样写的好处是 root 为空时第一条递归基立刻返回真，空树无需特判。

递归基第一条：a == null && b == null 返回 true：两棵空树互为镜像。这一条必须排在最前，它是所有递归分支最终的成功出口。

递归基第二条：a == null || b == null 返回 false：能走到这里说明不是「都为空」，那就是「恰好一个为空」，结构不对称。顺序颠倒会让「都为空」被误判为假，整棵树无论如何都返回假。

递归基第三条：a.val != b.val 返回 false：此时两者都非空，可以安全取值。对称要求对应位置值相等，不等即失败。

递归两支并用 && 连接：isMirror(a.left, b.right) && isMirror(a.right, b.left)：交叉配对是镜像的定义所在。写成 a.left 对 b.left 就变成了判断两树相同，[1,2,2,null,3,null,3] 会被误判为对称。用 && 而非 &，是为了让左侧失败时直接短路。

无需任何全局变量：每一层的返回值就是该层子问题的完整答案，逐层向上汇总即可。

以 [1,2,2,3,4,4,3] 走一遍（合法对称树，应返回 true）。这棵树的根是 1，左孩子是 2（其左 3、右 4），右孩子也是 2（其左 4、右 3）。

顶层调用 isMirror(1, 1)：都非空，值相等，展开成 isMirror(左2, 右2) && isMirror(右2, 左2)。

进入 isMirror(左2, 右2)：都非空，值都是 2，展开成 isMirror(左2的左=3, 右2的右=3) && isMirror(左2的右=4, 右2的左=4)。

isMirror(3, 3)：值相等，继续展开成 isMirror(null, null) && isMirror(null, null)，两者都命中第一条递归基返回 true，本层返回 true。

isMirror(4, 4)：同理返回 true。于是 isMirror(左2, 右2) 返回 true。

另一支 isMirror(右2, 左2) 是对称的镜像调用，同样返回 true。顶层得到 true && true，返回 true，正确。

再看反例 [1,2,2,null,3,null,3]：根是 1，左孩子 2 只有右孩子 3，右孩子 2 也只有右孩子 3。

isMirror(1,1) 展开成 isMirror(左2, 右2)。两者值都是 2，继续展开第一支 isMirror(左2的左, 右2的右) 即 isMirror(null, 3)：第一条递归基不成立（不是都为空），第二条成立（a 为空），返回 false。因为用的是 &&，第二支 isMirror(左2的右=3, 右2的左=null) 根本不会被计算，false 一路短路返回到顶层。

这个反例清楚地说明了为什么必须交叉配对：如果写成同侧配对，比较的是 isMirror(null, null) 和 isMirror(3, 3)，两者都成立，会得到错误的 true。

代码实现

class Solution {
    // 对原树调用 isMirror(root, root)。
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    private boolean isMirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        if (a.val != b.val) {
            return false;
        }

        return isMirror(a.left, b.right) && isMirror(a.right, b.left);
    }
}

func isSymmetric(root *TreeNode) bool {
    // 对原树调用 isMirror(root, root)。
    return isMirror(root, root)
}

func isMirror(a *TreeNode, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    if a.Val != b.Val {
        return false
    }

    return isMirror(a.Left, b.Right) && isMirror(a.Right, b.Left)
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是节点数。每个节点最多作为参数被访问常数次（在 isMirror(root, root) 的写法下，每个节点会在两条对偶的递归路径里各出现一次，仍是常数倍），每次只做值比较与空判断。发现不对称时会提前短路，实际访问量往往远小于 $n$。

空间复杂度：$O(h)$，其中 $h$ 是树高，来自递归栈。树平衡时是 $O(\log n)$，退化成链时是 $O(n)$。算法本身不使用任何额外数据结构；若改写成迭代版，需要一个队列成对存放待比较节点，空间同为 $O(n)$ 量级。

关键点总结

当问题描述的是「两个子结构之间的关系」，而给定签名只有一个参数时，必须另开双参数辅助函数。这个信号在对称二叉树、树的子结构、翻转等价二叉树里反复出现，是树形递归设计的第一课。

镜像与相同只差一处：孩子是交叉配对还是同侧配对。把这句话记牢，101 与 100 两道题的代码就能互相推导出来。

递归基的顺序即语义：先「都空为真」再「一空为假」。反过来写会把成功出口堵死。写多分支终止条件时，习惯性问一句「两个条件同时成立时该返回什么」，答案就决定了先后。

传 isMirror(root, root) 而非 isMirror(root.left, root.right)，可以让空树自然落进递归基、省掉一次判空；这类「让边界被主逻辑吞掉」的小设计是代码品味的体现。

不要试图把树压成一维序列再判回文：遍历序列会丢失空节点的位置信息，含重复值的树上必错。除非给空节点补占位符——那本质上已经是在比较结构了。

面试若被追问迭代写法，可用队列成对入队（每次推入 a.left/b.right 和 a.right/b.left），出队时也成对取出比较。能给出这个版本说明真正理解了「比较的单位是一对节点」。

易错点总结

递归写成同侧配对 isMirror(a.left, b.left) && isMirror(a.right, b.right)：这判断的是两树相同而非镜像，[1,2,2,null,3,null,3] 会被误判为 true，而它并不对称。

两条空判断顺序写反：先写 a == null || b == null 返回 false，则所有递归最终都会走到「两个空孩子」并返回假，任何树（包括 [1]）都返回 false。

只写 a == null && b == null 而漏掉「恰好一个为空」：[1,2] 递归到 isMirror(2, null) 时直接访问 b.val 抛空指针。

在主函数里没处理 root == null 又写成 isMirror(root.left, root.right)：空树入参立刻空指针；用 isMirror(root, root) 则天然规避。

递归两支用 & 而不是 &&：左侧已经确定失败，右侧仍会被完整展开，深树上白白多跑一整趟；虽然结果正确，但丢掉了提前失败的剪枝。

两支用 || 连接：只要有一侧对称就返回真，[1,2,3] 这类明显不对称的树会被误判。

比较值时用 a.val == b.val 却把节点类型换成了包装类型 Integer：值超过 127 时引用比较失效，[1000,1000,1000] 这类树会被误判为不对称；本题节点值是 int 无此问题，但换成对象树时要警惕。

用中序遍历序列判回文：[1,2,2,2,null,2] 的中序序列可能是回文，但树并不对称，会返回错误的 true。

迭代写法里逐个入队而非成对入队：队列里的配对关系被打乱，[1,2,2,3,4,4,3] 可能把 3 和 4 配到一起，结果随机出错。

误以为「左子树对称且右子树对称」就等于整棵树对称：[1,2,3] 的两棵子树各自都是单节点、都对称，但整棵树不对称，这个思路从一开始就跑偏了。

只比较结构不比较值：[1,2,3] 的结构完全对称，若漏掉 a.val != b.val 这一条会返回 true，而正确答案是 false。

相似题目

题目	难度	考察点
101. 对称二叉树	简单	与本题同题，可直接套用
100. 相同的树	简单	孩子改为同侧配对，是本题最直接的对照组
226. 翻转二叉树	简单	真的把左右孩子交换而非仅比较，也可先翻转再用 100 判等
剑指 Offer 27. 二叉树的镜像	简单	与 226 同题
951. 翻转等价二叉树	中等	允许任意节点翻转，每层要同时尝试交叉与同侧两种配对并取或
572. 另一棵树的子树	简单	外层枚举起点、内层调用同侧比较，双递归结构比本题多一层
617. 合并二叉树	简单	同为双指针同步递归，但要构造新树，空节点直接返回另一侧
104. 二叉树的最大深度	简单	单参数递归即可，返回值是数值而非布尔，是树形递归的最简形态
110. 平衡二叉树	简单	需要向上同时传递高度与是否平衡，用哨兵值合并两个返回值