LeetCode 101. 对称二叉树：递归的「双参数」形态

题目：「对称」的精确含义

LeetCode 101：判断二叉树是否轴对称——「对称」= 左子树与右子树互为镜像：

    1           对称：左 2 的左=右 3 的右，左 2 的右=右 3 的左
   / \
  2   2
 / \ / \
3  4 4  3

「镜像」不是「相等」：树的镜像 = 左右子树互换——「左子树与右子树互为镜像」的判定规则：两棵树 A、B 互为镜像 = A.root 值 == B.root 值 且 A.left 与 B.right 互为镜像 且 A.right 与 B.left 互为镜像——「交叉比较」（A 的左对 B 的右、A 的右对 B 的左——「镜像的交叉性」是本题的核心认知——普通「相等」是 A.left 对 B.left——「镜像打破左右的对齐」。

递归解：双参数的比较函数

递归的结构变化：本题的递归函数接收两个参数（左子树节点 a 与右子树节点 b）——「单参数递归」的局限（翻转二叉树的单参数是「自操作」——本题是「两两比较」——「参数的数量反映问题的结构」——「双参数递归」在树题中的普遍出现（LCA 的 p 与 q、相同树的 p 与 q——「两棵树/两个节点的比较」是双参数递归的标准场景。

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

def mirror(a, b):
    if not a and not b:
        return True           # 都空：对称
    if not a or not b:
        return False          # 一空一非空：不对称
    if a.val != b.val:
        return False          # 值不同：不对称
    return mirror(a.left, b.right) and mirror(a.right, b.left)

「三类失败情况」的枚举：「都空」对称、「一空一非空」不对称、「值不同」不对称——「null 的三种组合」（双参数递归的边界枚举——「都空」是合法的终止（不是错误——与「一空一非空」区分——「都空=True」容易被误写成 False——「空节点也是节点」的对称观——「null 的组合枚举」是树递归边界的系统性方法——三个 if 覆盖全部组合。

「交叉递归」的追踪验证（四层对称树）：mirror(2L, 2R) → mirror(3LL, 3RR) 且 mirror(4LR, 4RL)——「交叉的递归树」——递归树的每层是「一对对节点」——「递归树」的画法（节点对为节点——「对」是本题递归树的原子——「验证」用四层小树手推——与翻转二叉树篇的「小例子验证」方法一致。

迭代解：BFS 的「双队列」

迭代的思想：递归的镜像比较可以「一层层比较」——「双队列」：左队列按「左→右」进、右队列按「右→左」进——「出队时成对比较」——「两个队列的对称遍历」：

from collections import deque

def is_symmetric(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

「成对入队」的形态：队列元素是「节点对」（不是单节点——「对的队列」保持比较的成对性——「continue」的空对处理（都空跳过——「跳过而非返回」因为后面还有其他对——「BFS 的成对遍历」与递归的镜像等价——「递归与 BFS 的空间对比」：递归 O(h)（栈）、BFS O(w)（宽度——「平衡树 O(log n) vs O(n/2)」——「空间的选择」按树的形状——链状树递归省、满树 BFS 省——「没有绝对的优，只有树的形状」**——与可中断性篇的「树形状决定空间」呼应。

「对称」的另一种视角：「树的中序遍历回文」——对称树的中序遍历是回文序列——「中序回文」的必要不充分（回文中序不一定对称——结构可能不对称——「必要不充分」的条件要警惕——「值序列验证」的陷阱——「结构」必须递归或成对比较——「单序列验证」的失效——这个陷阱能讲清楚，说明对树结构的理解到位。

对称二叉树的进阶：双参数递归的深入与树题的「关系类」家族

对称二叉树的进阶：双参数递归的深入与「关系类」树题的系统梳理。「双参数递归的深入理解」：「双参数的本质」——递归函数的参数从「一个节点」变成「一对节点」——「一对节点」的语义（「这两个节点（连同子树）满足关系 X 吗」——「关系」的类型：镜像关系（对称树）、相同关系（相同树）、祖先关系（LCA）——「关系递归」的转移：当前对的判定 + 子对的递归——「镜像的转移」：mirror(a,b) = a.val==b.val && mirror(a.left,b.right) && mirror(a.right,b.left)——「交叉」——「相同的转移」：same(a,b) = a.val==b.val && same(a.left,b.left) && same(a.right,b.right)——「对齐」——「镜像 vs 相同」的差异：交叉 vs 对齐——「一个字的差异」——「交叉与对齐」的对比——「关系类树题的通用模板」——「模板的三部分」：null 组合枚举 + 值比较 + 子关系递归——「三部分」的固定——「只变递归的交叉方向」——「变体只改递归方向」——「模板复用」——「对称、相同、子树判断」的模板复用。「null 组合的系统枚举」：「四种组合」：都空（终止返回 true）、A 空 B 非空（false）、A 非空 B 空（false）、都非空（值比较+子递归）——「四种」覆盖所有情况——「三种 if」的写法——「合并的写法」（if not a or not b: return a is b——「一行合并」的简洁——「a is b」——「都空时 a==b==None → True」——「一行合并」的巧妙——「可读性 vs 简洁」——「面试建议分开写」（清晰——「合并」是优化后的形态——「两版的取舍」。「关系类树题的家族」：「家族一：相同树（100）」——对齐递归——「家族二：子树判断（572）」——「子树的判断」——A 的某个子树与 B 相同——「两层递归」——外层遍历 A 找匹配点 + 内层 same 比较——「子树判断」的组合——「家族三：路径总和（112/113）」——「路径的递归」——「单参数+目标值」——「目标值的递减」——「路径和」的递归——「家族四：LCA（236，库内已有）」——「双参数的 LCA」（p 和 q——「LCA 的递归」——「左右子树的结果合并」——「LCA」是双参数递归的巅峰——「四个家族」的共性：「双参数（或多参数）递归 + null 枚举 + 关系判定」——「共性」让四个题目一通百通。对称二叉树的进阶总结：双参数递归的深入（关系类型、交叉 vs 对齐、null 四组合）+关系类家族（相同/子树/路径/LCA）的模板复用+迭代 BFS 的成对遍历——「双参数递归」是树题的「第二形态」——从「单参数自操作」到「双参数互比较」——「形态的升级」——「对称树」就是这个升级的入门考试——「通过了它，LCA 与相同树就是同一模板的变奏——「变奏」不需要新思维，只需要改「交叉方向」和「关系判定」——「这就是模板复用的力量。

对称树的三个追问：序列判断为何失效、栈版怎么写、镜像与翻转的互推

「把中序序列反过来对比，回文就对称——为什么不行？」——这是本题最常见的错误解法。反例不难构造：两棵树的中序同为 2、2、2，一棵结构对称、一棵右子树歪在一侧——值序列相同而结构不对称。更本质的原因：单个遍历序列是「丢结构」的投影——同一组值可以还原出多种树形（这也是「中序+前序才能重建树」的原因），而对称是结构性质，值的回文只是必要条件。同理，「层序序列逐层回文」也不行：null 的分布位置不同就能造出反例——想让序列判断成立，必须把 null 也作为占位符写进序列，而这时的「序列比对」在信息量上已经等价于成对的结构比较了——绕一圈又回到递归，只是把调用栈换成了序列的隐式展开。「迭代版除了双队列，还能怎么写？」——把 BFS 换成 DFS：显式栈里成对压入左右交叉的两对节点，弹出时做同样的三类检查——「成对」的本质不变，变的只是遍历顺序；栈版的空间是 O(h)（深树省）、队列版是 O(w)（宽树省），与正文的空间对比结论一致。写栈版有个细节：空对的处理用 continue 跳过而不是返回真——栈里还有别的对等着检查，这与递归里「都空返回 True 但别短路兄弟子树」是同一个道理。「镜像、相同、翻转三个概念能互推吗？」——能，而且互推本身就是面试加分项：翻转是操作（invert）、镜像是关系（互为翻转）、相同是另一组关系（对齐比较）。由此得到两个恒等式：t 与 invert(t) 相同，等价于 t 对称；mirror(a, b) 等价于 same(a, invert(b))——后者说明对称判断可以用「翻转 + 判等」两个现成零件拼出来，只是多花 O(n) 的复制开销，不如交叉递归一趟干净——「能用组合拼出来」与「知道最优形态」是两个层次，面试里先给组合方案再给交叉递归，展示的是思维的完整过程。对称判断还有个工程影子：可视化与布局工具里的「水平镜像」按钮、构图算法中的轴对称校验，底层都是这趟交叉比较——结构对称性是图形与编辑器里廉价又常用的不变量。

「三类检查的顺序能调换吗——先判值再判空行不行？」——不行，这是双参数递归的固定次序：null 枚举 → 值比较 → 子递归，三段不可交换。原因很直接：取 a.val 之前必须先确认 a 非空，判空是判值的前置守卫——把值比较提前，空指针就先于逻辑判断发生。次序背后的原则是「先排除非法状态，再比较有效状态」——这与迭代版里「先 continue 空对、再比较非空对」的顺序完全一致，两种实现共享同一个守卫结构，记住了递归的次序，迭代版就自动不会写错。

小结

对称二叉树的完整解析：镜像的判定（「交叉比较」：A.left 对 B.right、A.right 对 B.left——镜像打破左右对齐）；双参数递归（mirror(a, b)——三类失败情况（都空 true、一空一非空 false、值不同 false）——「null 组合的枚举」是树递归边界的系统方法）；迭代双队列（成对入队出队——BFS 的对称遍历——「空间对比」：递归 O(h) vs BFS O(w)）；陷阱（中序回文是必要不充分——「单序列验证」失效——结构必须成对比较）。给学习者的进阶意义：双参数递归是树题的「第二形态」——从「单参数自操作」（翻转）到「双参数互比较」（对称、相同、LCA）——「两个节点/两棵树的关系题」全用这个模板——三个 if 的边界枚举（都空/一空/值不同）+ 递归的交叉调用——掌握这个模板，树的「关系类」题目就通了。

对称二叉树教的不只是对称，是「递归函数的参数可以是『一对』」——当问题涉及两个对象的关系时，递归的签名自然升级——这个升级在相同树、LCA、合并树等所有「关系类」树题中反复出现。