对称二叉树

给你一个二叉树的根节点 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

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

解法一（递归 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) {
        if (left == nullptr && right == nullptr)
        {
            return true;
        }

        if (left == nullptr || right == nullptr)
        {
            return false;
        }

        if (left->val != right->val)
        {
            return false;
        }

        return isMirror(left->left, right->right) &&
               isMirror(left->right, right->left);
    }
};

解法二（迭代队列）：

/**
 * 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;
        }

        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;
    }
};

核心思想

判断一棵树是否对称，不能只看每一层的值是否左右相同。

真正要判断的是：左子树和右子树是否互为镜像。

镜像关系要求两个节点同时满足：

• 两个节点的值相等
• 左节点的左子树，要和右节点的右子树镜像
• 左节点的右子树，要和右节点的左子树镜像

这题最关键的观察是：

对称二叉树的判断，本质是成对比较“外侧节点”和“内侧节点”。

所以递归时不能只比较 left->left 和 right->left。

而是要交叉比较：

left->left  和 right->right
left->right 和 right->left

解法一：递归 DFS

定义递归函数：

bool isMirror(TreeNode* left, TreeNode* right)

它表示：

以 left 为根的子树，和以 right 为根的子树是否互为镜像

递归中分几种情况。

如果两个节点都为空：

return true;

说明这两边都没有节点，是对称的。

如果只有一个为空：

return false;

说明结构已经不对称。

如果两个节点都不为空，但值不同：

return false;

说明节点值不对称。

最后，继续比较外侧和内侧：

return isMirror(left->left, right->right) &&
       isMirror(left->right, right->left);

只有这两个方向都对称，当前两棵子树才互为镜像。

解法二：迭代队列

递归本质上是在不断成对比较节点。

所以也可以用队列手动保存待比较的节点对。

初始时，把根节点的左右孩子放入队列：

q.push(root->left);
q.push(root->right);

之后每次从队列中取出两个节点：

TreeNode* left = q.front();
q.pop();

TreeNode* right = q.front();
q.pop();

这两个节点应该互为镜像。

如果它们都为空，说明这一对位置是对称的，继续检查下一对。

如果只有一个为空，或者两个值不同，直接返回 false。

如果这一对节点本身匹配，就继续把它们的外侧和内侧节点成对放入队列：

q.push(left->left);
q.push(right->right);

q.push(left->right);
q.push(right->left);

队列为空时，说明所有应当镜像的位置都检查完成，返回 true。

为什么必须交叉比较

对于一棵对称二叉树：

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

根节点左右两边的结构是镜像关系。

左子树的外侧节点是 3，对应右子树的外侧节点也是 3。

左子树的内侧节点是 4，对应右子树的内侧节点也是 4。

所以比较时必须是：

左的左  vs  右的右
左的右  vs  右的左

如果错误地比较：

左的左  vs  右的左
左的右  vs  右的右

那是在判断两棵子树是否完全相同，而不是判断它们是否互为镜像。

边界情况

如果 root == nullptr，空树可以看作对称。

不过本题节点数量至少为 1，这个判断仍然保留，让代码更通用。

如果只有一个根节点：

root = [1]

左右子树都为空，所以是对称二叉树。

如果某一对镜像位置中，一个为空，一个不为空，说明结构不对称，直接返回 false。

如果某一对镜像位置的值不同，也直接返回 false。

正确性证明

我们证明：两个解法都能正确判断二叉树是否轴对称。

结论 1：递归函数的含义正确

isMirror(left, right) 用来判断两棵子树是否互为镜像。

如果两者都为空，它们互为镜像。

如果只有一个为空，它们结构不同，不可能互为镜像。

如果两者都不为空但值不同，也不可能互为镜像。

如果两个节点值相同，那么还需要满足：

• left->left 和 right->right 互为镜像
• left->right 和 right->left 互为镜像

这正好符合镜像二叉树的定义。

因此递归函数的判断逻辑正确。

结论 2：递归解法不会遗漏任何需要比较的位置

从根节点的左右子树开始，递归会继续比较外侧节点和内侧节点。

每一层都会把当前镜像节点对拆成下一层的两组镜像节点对。

因此所有对称位置都会被检查到。

只要有任意一对结构不一致或值不一致，递归都会返回 false。

结论 3：迭代队列保存的始终是应该互为镜像的节点对

初始时，队列中保存的是 root->left 和 root->right，它们确实应该互为镜像。

每次取出一对节点并判断通过后，算法把它们的外侧节点和内侧节点分别加入队列。

这些新加入的节点对，也正是镜像定义中下一步需要比较的节点对。

所以队列中始终保存的是应该互为镜像的节点对。

结论 4：迭代解法能正确发现所有不对称情况

对于每一对从队列中取出的节点：

• 如果一个为空一个不为空，算法返回 false
• 如果两个都不为空但值不同，算法返回 false
• 如果两个都为空，说明这一对位置对称
• 如果两个都不为空且值相同，算法继续检查下一层镜像节点对

因此只要树中存在结构或值不对称的位置，算法一定会发现。

如果队列最终为空，说明所有镜像位置都检查通过，所以整棵树对称。

得出结论

由结论 1 和结论 2 可知，递归 DFS 解法正确。

由结论 3 和结论 4 可知，迭代队列解法正确。

因此两个解法都能正确判断二叉树是否轴对称。

举例理解

以：

root = [1,2,2,3,4,4,3]

为例，这棵树可以表示为：

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

从根节点左右孩子开始比较：

所有镜像位置都匹配，所以返回：

true

再看：

root = [1,2,2,null,3,null,3]

可以理解为：

      1
    /   \
   2     2
    \     \
     3     3

左子树的内侧有 3，右子树的内侧位置却为空。

结构不对称，所以返回：

false

复杂度分析

设二叉树节点数为 n，树的高度为 h。

解法一

每个节点最多被递归访问一次。

• 时间复杂度：O(n)
• 空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

每个节点最多入队一次、出队一次。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

队列在最宽的一层可能保存 O(n) 个节点。

如果想写得最简洁，递归解法更推荐；如果要满足进阶中的迭代要求，可以使用队列解法。