对称二叉树
Symmetric Tree
判断二叉树是否关于根节点左右对称（形状和值都要镜像）。
在力扣中练习题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
解题思路
主解法
递归 · 镜像比较
比较两棵子树时，左孩子的左孩子对右孩子的右孩子
对称不是“左子树等于右子树”，而是“左子树和右子树互为镜像”。所以比较两个节点 a、b 时，不能把它们的孩子按相同方向配对：
- a 的左孩子，要和 b 的右孩子比；
- a 的右孩子，要和 b 的左孩子比。
分步图解
从根的两个孩子开始；根节点本身不需要比较，只有左右子树需要互为镜像。
镜像比较 · 蓝左橙右
终止条件有三种：两个都为空，返回 true；只有一个为空，返回 false；值不相等，返回 false。三者顺序不能反，否则空指针会在取值时崩溃。
自拟树根的两个孩子都是 4，但它们的子树方向相反：左 4 的左孩子 2 对应右 4 的右孩子 2，左 4 的右孩子 7 对应右 4 的左孩子 7。画面上两个 4、两个 2、两个 7 都靠节点身份区分。
图解
镜像比较 · 蓝左橙右
普通节点当前操作已确认 / 结果待处理 / 对照
每个节点最多被比较一次，时间 O(n)，空间 O(h)。
时间 O(n)空间 O(h)
易错点
- 比较 a.left 与 b.left：得到的是“两棵子树相同”，不是镜像；本题根的两个孩子值相同，更容易误判。
- 先取 val 再判空：只有一个孩子为空时会解引用空指针。
- 只比较根的两个孩子：子树内部没有继续镜像比较。
对照解法
队列 · 成对比较
每次取出一对节点，按镜像顺序把孩子成对入队
逻辑与递归等价，但队列最坏保存 O(n) 个节点；递归版空间只占树高。
把需要比较的节点成对放进队列。每次取出两个：都为空就跳过；只有一个为空或值不同就失败。然后把 a.left 与 b.right、a.right 与 b.left 成对入队。
这种写法把递归的隐式栈换成了显式队列，层序检查的直觉更强，也不受递归深度限制。代价是队列里可能同时存在很多对节点。
注意入队顺序本身不重要，重要的是每一对必须是镜像位置。
- 1根为空返回 true，否则把左右孩子成对入队。
- 2每次弹出两个节点。
- 3都空继续；一空或值不同返回 false。
- 4按镜像顺序把孩子成对入队。
时间 O(n)空间 O(n)
易错点
- 入队顺序写成 a.left,b.left：变成同向比较。
- 空节点没有成对入队：会漏掉“一侧为空另一侧不为空”的情况。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
root = [5,4,4,2,7,7,2]从根的两个孩子开始；根节点本身不需要比较，只有左右子树需要互为镜像。
镜像比较 · 蓝左橙右
查看 C++ 代码
延伸阅读
- 对称、翻转、判断两棵树是否相同，区别都在“孩子如何配对”。
- 空节点不是可以直接跳过的细节：它决定了形状是否镜像。