Appearance
判断对称二叉树：镜像同步遍历
本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。判断对称二叉树是「二叉树基础」这一考点的代表题，也是练习"用一次递归同时驱动两个指针"这种写法的好材料。它是经典训练题，不是真题，也不押题。
题目
给定一棵二叉树，判断它是否关于根结点左右对称。也就是说，把这棵树沿根结点画一条竖线对折，左右两半应该完全重合——不仅结构对称，每个对称位置上的结点值也要相等。例如根为 1、左孩子为 2（左 3 右 4）、右孩子为 2（左 4 右 3）的树是对称的；根为 1、左孩子为 2（左空右 3）、右孩子为 2（左空右 3）的树不对称（两个 3 都长在右边，折过去对不上）。设计算法判断给定二叉树是否对称。
这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把递归时的配对方向写对。
直观解法：一个镜像判断函数,同步递归
「对称」这个词本身就在暗示做法：一棵树对称,等价于它的左子树和右子树互为镜像。互为镜像的关键是交叉相等——左子树的左孩子要对上右子树的右孩子,左子树的右孩子要对上右子树的左孩子,这跟「两棵子树长得一样」不是一回事。于是设计一个专门判断「两棵子树是否互为镜像」的函数 isMirror(l, r),同步递归地把这个交叉关系一路核对下去。
c
#include <stdbool.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
bool isMirror(TreeNode *l, TreeNode *r) {
if (l == NULL && r == NULL) return true; // 都空,这一层对称
if (l == NULL || r == NULL) return false; // 一空一非空,肯定不对称
if (l->data != r->data) return false; // 值不等,不对称
// 交叉配对:l 的左孩子对 r 的右孩子,l 的右孩子对 r 的左孩子
return isMirror(l->left, r->right) && isMirror(l->right, r->left);
}
bool isSymmetric(TreeNode *root) {
if (root == NULL) return true; // 空树视为对称
return isMirror(root->left, root->right);
}拿开头那棵对称树走一遍：isMirror(2,2) 值相等,继续交叉递归——isMirror(3,3)（左子树的左孩子 3 对右子树的右孩子 3）和 isMirror(4,4)（左子树的右孩子 4 对右子树的左孩子 4）,两边都是叶子对叶子、值相等,全部返回 true。再拿不对称的例子走一遍：isMirror(2,2) 值相等,交叉递归到 isMirror(null, 3)——一空一非空,立刻返回 false。
复杂度：每个结点作为 l 或 r 恰好被访问一次,时间
为什么它就是满分解
这道题没有「暴力 vs 最优」的分差。用总纲的「找浪费三问」审一遍,三问全部答「没有」：
- 有没有重复扫描？ 没有。每对结点只在各自那一层被比较一次,比过就不再回头。
- 有没有重算已知的东西？ 没有。每一层的「是否对称」直接由子问题的布尔结果
&&得出,没有任何值被重复推导。 - 有没有放着性质不用？ 没有。题目要判断的「镜像对称」性质,正好被
isMirror的交叉递归结构直接承载,不需要额外的辅助信息。
更根本的一条：判断是否对称,至少要把树上每一个结点都看一遍（少看一个,就可能漏掉一处不对称）——遍历一遍就是
真正的难点在交叉配对
分不在优化上,在把递归的配对方向写准：
- 交叉,不是并排。最容易写错的地方是把
isMirror(l->left, r->right)手滑写成isMirror(l->left, r->left)——那是在判断两棵子树「长得一样」（结构相同、值相同）,不是判断「互为镜像」。对折之后,左边的左孩子应该落在右边的右孩子那一侧,这个交叉关系一旦记反,对称树会被误判成不对称,而某些「长得一样」的非对称树反而会被误判成对称。 - 两个空指针的判断顺序。必须先判
l == NULL && r == NULL（都空,对称）,再判l == NULL || r == NULL（一空一非空,不对称）,最后才轮到取l->data。顺序反了,或者漏了第一条直接去比l->data,会在空指针上直接崩掉。 - 空树本身视为对称。
isSymmetric里root == NULL要单独返回true——一棵没有结点的树,谈不上「不对称」,题目通常也把它算作对称的特例。
三处任何一处出错,代码依然「跑得动」（除非踩到空指针崩溃）,但会在某些用例上判错。这正是「不用优化、把细节写对」这类题的共同特点。
交叉递归,看一遍
用一棵四层结构但对称的树演示：根 1，左孩子 2（左 3、右 4），右孩子 2（左 4、右 3）。注意 isMirror 递归时如何把左子树的左孩子 3 和右子树的右孩子 3 配成一对，把左子树的右孩子 4 和右子树的左孩子 4 配成另一对：
演示为 JavaScript 版本，逻辑与上文 C 代码一一对应（演示驱动用的是对称树；可自行改成 4 结点里任意一个值，观察交叉配对失败时如何提前返回 false）。
别画蛇添足
这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：
- 想先做一次序列化再比较。把左子树和右子树分别按某种遍历序列化成字符串,再判断两个字符串是否互为镜像——这多做了一次遍历和字符串拼接,而且序列化时空结点的占位方式稍有不慎就会引入新的 bug（比如漏掉空结点占位,导致结构不同的树序列化后字符串却相同）。递归交叉配对已经是一遍到位的写法,没必要绕这一圈。
- 想用层序遍历逐层比较每层是否回文。这个思路本身没错,但实现起来要把每一层的结点值（包括空位）收集成数组再判断回文,比递归多了一层数组管理的复杂度,还容易在「用什么值表示空位」上出错。递归版本用调用栈免费维护了「当前比较到哪一对结点」,不用自己额外维护队列和层信息。
下一步
- 看层序遍历的交互演示（对称判断常配合层序结构理解）：层序遍历可视化
- 回到方法论源头：「暴力解到最优解」真题专题总纲