101. 对称二叉树 (Symmetric Tree)

示例说明

示例 1：

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

结构展示：

Plaintext

示例 2：

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

结构展示：

Plaintext

提示条件

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

进阶挑战

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

判断一个二叉树是否轴对称，本质上是在考察镜像结构。一个二叉树如果是对称的，那么它的左子树和右子树必须互为镜像。

1. 核心思路：第一性原理拆解

我们要判断两棵树（假设为 $L$ 和 $R$ ）是否互为镜像，必须同时满足以下三个条件：

根节点值相等： $L.val = R.val$ 。
外侧对称： $L$ 的左子树与 $R$ 的右子树互为镜像。
内侧对称： $L$ 的右子树与 $R$ 的左子树互为镜像。

这是一种典型的递归定义。如果根节点为空，它显然是对称的。如果根节点存在，我们就开始比较它的左孩子和右孩子。

2. 递归实现（DFS）

这是最直观的解法。我们定义一个辅助函数 isMirror 来处理两个节点的比较。

代码实现：

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (!root) return true;

    const isMirror = (l, r) => {
        // 1. 同时为空，对称
        if (!l && !r) return true;
        // 2. 一个为空或值不相等，不对称
        if (!l || !r || l.val !== r.val) return false;
        
        // 3. 递归比较：左的左 vs 右的右（外侧） AND 左的右 vs 右的左（内侧）
        return isMirror(l.left, r.right) && isMirror(l.right, r.left);
    };

    return isMirror(root.left, root.right);
};

3. 迭代实现（BFS/队列）

如果你担心树的深度过大导致递归栈溢出，或者面试官要求非递归解法，可以使用队列（Queue）来模拟递归的过程。其逻辑是：成对地将需要比较的节点放入队列。

思路：

初始化一个队列，将 root.left 和 root.right 入队。
每次从队列中取出两个节点 $u$ 和 $v$ 。
判断 $u$ 和 $v$ 是否满足镜像条件：
- 都为空：继续下一轮循环。
- 其中一个为空或值不等：返回 false。
将 $u$ 的左孩子和 $v$ 的右孩子成对入队（外侧比较）。
将 $u$ 的右孩子和 $v$ 的左孩子成对入队（内侧比较）。

代码实现：

JavaScript

var isSymmetric = function(root) {
    if (!root) return true;
    
    // 使用队列存储成对比较的节点
    let queue = [root.left, root.right];
    
    while (queue.length > 0) {
        let l = queue.shift();
        let r = queue.shift();
        
        if (!l && !r) continue;
        if (!l || !r || l.val !== r.val) return false;
        
        // 注意入队顺序，确保下次取出的两个是镜像位置的节点
        queue.push(l.left, r.right); // 外侧
        queue.push(l.right, r.left); // 内侧
    }
    
    return true;
};

4. 复杂度分析

无论是递归还是迭代，我们都需要遍历整棵树的所有节点。

时间复杂度： $O(n)$ ，其中 $n$ 是二叉树的节点数。每个节点最多被访问一次。
空间复杂度：
- 递归版： $O(h)$ ，其中 $h$ 是树的高度。最坏情况下（树退化为链表）为 $O(n)$ ，平均情况下为 $O(\log n)$ 。
- 迭代版： $O(n)$ 。在最坏情况下，队列中可能需要存储接近一层的节点。

总结

处理树的镜像问题，关键在于打破“左右对称”的思维惯性，转化为“内外对应”的逻辑。

如果你对二叉树的其他变形题（如：翻转二叉树、判定相同树）感兴趣，我也可一并为你梳理它们的内在联系。需要我继续讲解相关题目吗？

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { if (!root) return true; const isMirror = (l, r) => { // 1. 同时为空，对称 if (!l && !r) return true; // 2. 一个为空或值不相等，不对称 if (!l || !r || l.val !== r.val) return false; // 3. 递归比较：左的左 vs 右的右（外侧） AND 左的右 vs 右的左（内侧） return isMirror(l.left, r.right) && isMirror(l.right, r.left); }; return isMirror(root.left, root.right); };

var isSymmetric = function(root) { if (!root) return true; // 使用队列存储成对比较的节点 let queue = [root.left, root.right]; while (queue.length > 0) { let l = queue.shift(); let r = queue.shift(); if (!l && !r) continue; if (!l || !r || l.val !== r.val) return false; // 注意入队顺序，确保下次取出的两个是镜像位置的节点 queue.push(l.left, r.right); // 外侧 queue.push(l.right, r.left); // 内侧 } return true; };

101. 对称二叉树 (Symmetric Tree)