【LeetCode 101】对称二叉树：如何用递归编写一面“镜子”？

判断一棵二叉树是否“轴对称”，就像是把这棵树沿着中间的轴折叠，看左右两边能不能完美重合。或者简单来说，就是左子树是右子树的镜像。

这道题是 LeetCode 100. 相同的树 的变体。在“相同的树”中，我们比对的是“左 vs 左”和“右 vs 右”；而在“对称二叉树”中，我们需要比对的是**“左 vs 右”**。

1. 核心思路：把“一”变成“二”

源码如下：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftT,TreeNode rightT){
        if(leftT == null && rightT == null ) return true;
        if(leftT != null && rightT == null ) return false;
        if(leftT == null && rightT != null ) return false;
        if(leftT.val != rightT.val) return false;
        return isSymmetricChild(leftT.left,rightT.right) && isSymmetricChild(leftT.right,rightT.left);

    }
}

单独看一棵树很难写递归，我们需要转换视角：

1. 根节点自己不需要比（或者说它就是轴）。
2. 问题转化为：根节点的左子树 (root.left) 和根节点的右子树 (root.right) 之间是否互为镜像？

于是，我们引入了一个辅助函数 isSymmetricChild(leftT, rightT)，让两棵子树同时开始赛跑。

2. 代码深度拆解

这段代码逻辑非常清晰，我们可以将其分为 终止条件 和 递归逻辑 两部分。

A. 终止条件（判空与判值）

这部分逻辑和“判断相同的树”几乎一模一样。我们需要处理指针走到空的情况：

public boolean isSymmetricChild(TreeNode leftT, TreeNode rightT) {
    // 1. 两个指针都走到头了（都为 null），说明之前的路径都匹配 -> 成功
    if (leftT == null && rightT == null) return true;
    
    // 2. 一个空一个不空，说明不对称（长短不一） -> 失败
    if (leftT != null && rightT == null) return false;
    if (leftT == null && rightT != null) return false;
    
    // 3. 两个都有节点，但值不一样 -> 失败
    if (leftT.val != rightT.val) return false;
    
    // ... 递归部分
}

B. 递归逻辑（镜像法则）

这是整道题的灵魂所在。
要两棵树互为镜像，必须满足以下两个条件同时成立（AND）：

1. 外侧对比：左树的左孩子 == 右树的右孩子。
2. 内侧对比：左树的右孩子 == 右树的左孩子。

    //                root
    //              /      \
    //          leftT      rightT
    //          /   \      /    \
    //         L1    R1   L2     R2
    
    // 镜像规则：
    // 1. L1 必须等于 R2 (leftT.left vs rightT.right) -> 外侧
    // 2. R1 必须等于 L2 (leftT.right vs rightT.left) -> 内侧

    return isSymmetricChild(leftT.left, rightT.right) && // 外侧互相对比
           isSymmetricChild(leftT.right, rightT.left);   // 内侧互相对比

代码精准地捕捉到了这一点：left 对应 right，right 对应 left，这就是“镜像”在代码层面的体现。

3. 图解“外侧”与“内侧”

为了更直观地理解，我们可以想象两个指针 p 和 q：

• p 从左边树出发，往左走；q 必须从右边树出发，往右走（向两边张开，检查外侧）。
• p 从左边树出发，往右走；q 必须从右边树出发，往左走（向中间靠拢，检查内侧）。

只有当这一张一合都匹配时，才是对称的。

4. 复杂度分析

• 时间复杂度：$O(N)$。我们需要遍历树中的每一个节点一次。
• 空间复杂度：$O(H)$。即递归栈的深度，$H$ 为树的高度。

5. 总结

LeetCode 101 的解题口诀就是：“左对右，右对左，值相等，空对空”。

通过这道题，我们再次复习了二叉树的递归套路：

1. Base Case：处理 null 和 val 不相等的情况。
2. Recursive Step：根据题目要求（是相同还是镜像），决定递归参数的对应关系。
   • 相同的树：left 对 left，right 对 right。
   • 对称的树：left 对 right，right 对 left。

只要改动一行递归调用的参数顺序，就能解决完全不同的几何结构问题，这就是递归的魅力。