🔗 对称二叉树

题目来源：101. 对称二叉树 – 力扣（LeetCode）

📌 题目描述

给你一个二叉树的根节点 root，检查它是否轴对称。

即：二叉树是否以根节点为中心，左右两棵子树互为镜像。

✅ 示例解析

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
解释：左子树 [2,3,4] 与右子树 [2,4,3] 互为镜像，整体结构对称。

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false
解释：左子树为 [2,null,3]，右子树为 [2,null,3]，但位置不对称（左子树的右孩子 vs 右子树的右孩子），不满足镜像条件。

示例 3：

输入：root = [1]
输出：true
解释：单个节点天然对称。

⚠️ 提示

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

💡 解法：递归（双指针镜像比较）—— O(n) 时间，O(h) 空间

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root.left, root.right);
    }

    public boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  最坏情况下需要遍历所有节点（每个节点被访问一次），因此时间复杂度为 O(n)。
• 空间复杂度：O(h)
  递归调用栈的深度取决于树的高度 h。最坏情况（链状树）为 O(n)，平均情况（平衡树）为 O(log n)。

🧩 解题思路

核心思想：镜像对比
判断一棵树是否对称，等价于判断它的左子树和右子树是否互为镜像。

如何判断两棵树互为镜像？

1. 它们的根节点值相等；
2. 第一棵树的左子树 与 第二棵树的右子树 对称；
3. 第一棵树的右子树 与 第二棵树的左子树 对称。

这天然适合用递归实现。

递归终止条件：

• 两个节点都为空 → 对称 ✅
• 其中一个为空或值不等 → 不对称 ❌