05、对称二叉树

哈喽，大家好，我是厨子，今天给大家分享一个题目，对称二叉树

https://leetcode.cn/problems/symmetric-tree/description/?envType=problem-list-v2&envId=binary-tree

题目描述

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

示例 1:

输入：root = [1,2,2,3,4,4,3]
输出：true
        1
       / \
      2   2
     / \ / \
    3  4 4  3

这是一个对称的二叉树

示例 2:

输入：root = [1,2,2,null,3,null,3]
输出：false
        1
       / \
      2   2
       \   \
        3   3

这不是对称的二叉树

约束条件:

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

进阶: 你可以运用递归和迭代两种方法解决这个问题吗？

什么是对称二叉树？

对称的定义

一棵二叉树是对称的，需要满足：

1. 根节点的左子树和右子树镜像对称
2. 左子树的左子节点 = 右子树的右子节点（值相同）
3. 左子树的右子节点 = 右子树的左子节点（值相同）

对称的例子:
        1
       / \
      2   2
     / \ / \
    3  4 4  3

左子树:     右子树:
    2           2
   / \         / \
  3   4       4   3

镜像对称 ✓


不对称的例子:
        1
       / \
      2   2
       \   \
        3   3

左子树:     右子树:
    2           2
     \           \
      3           3

不是镜像 ✗

镜像对称的规律

1. 左节点的值与右节点的值相等。
2. 左节点的左子树和右节点的右子树呈镜像对称关系。
3. 左节点的右子树和右节点的左子树呈镜像对称关系。

哎嘛，读着好绕口

解题思路

核心思想

这道题是 相同的树的变体

相同的树: 比较两棵树是否完全相同

对称二叉树: 比较左右子树是否镜像对称

相同 vs 镜像

判断两棵树相同:
左树的左子树 vs 右树的左子树
左树的右子树 vs 右树的右子树

判断两棵树镜像:
左树的左子树 vs 右树的右子树  ← 交叉比较！
左树的右子树 vs 右树的左子树  ← 交叉比较！

图解示例

示例1：对称的树 [1,2,2,3,4,4,3]

        1
       / \
      2   2
     / \ / \
    3  4 4  3

步骤1: 比较左子树(2)和右子树(2)
  值相同: 2 == 2 ✓

步骤2: 递归比较
  左.左(3) vs 右.右(3): 3 == 3 ✓
  左.右(4) vs 右.左(4): 4 == 4 ✓

步骤3: 继续递归
  所有叶子节点都对称

结果: true

示例2：不对称的树 [1,2,2,null,3,null,3]

        1
       / \
      2   2
       \   \
        3   3

步骤1: 比较左子树(2)和右子树(2)
  值相同: 2 == 2 ✓

步骤2: 递归比较
  左.左(null) vs 右.右(3): null != 3 ✗

结果: false

代码实现

递归（DFS）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        // 比较左右子树是否镜像对称，这里注意传参
        return isMirror(root->left, root->right);
    }

private:
    // 判断两棵树是否镜像对称
    bool isMirror(TreeNode* left, TreeNode* right) {
        // 情况1: 都为空 → 对称
        if (left == nullptr && right == nullptr) {
            return true;
        }

        // 情况2: 其中一个为空 → 不对称
        if (left == nullptr || right == nullptr) {
            return false;
        }

        // 情况3: 值不同 → 不对称
        if (left->val != right->val) {
            return false;
        }

        // 递归比较（注意是交叉比较）:
        // 左树的左子树 vs 右树的右子树
        // 左树的右子树 vs 右树的左子树
        return isMirror(left->left, right->right) &&
               isMirror(left->right, right->left);
    }
};

时间复杂度: O(n)，n 是节点总数，每个节点访问一次

空间复杂度: O(h)，h 是树的高度（递归栈深度）

迭代（BFS + 队列）

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }

        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);

        while (!q.empty()) {
            TreeNode* left = q.front();
            q.pop();
            TreeNode* right = q.front();
            q.pop();

            // 都为空，继续
            if (left == nullptr && right == nullptr) {
                continue;
            }

            // 其中一个为空，或值不同
            if (left == nullptr || right == nullptr) {
                return false;
            }
            if (left->val != right->val) {
                return false;
            }

            // 按镜像顺序加入队列
            q.push(left->left);
            q.push(right->right);  // 交叉！
            q.push(left->right);
            q.push(right->left);   // 交叉！
        }

        return true;
    }
};

时间复杂度: O(n)

空间复杂度: O(w)，w 是树的最大宽度