LeetCode 101. 对称二叉树：递归与迭代解法详解

h 为树的高度，n 为节点总数

代码实现

Java 实现

// 方法一：递归法
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        // 两个都为空，对称
        if (left == null && right == null) {
            return true;
        }
        // 一个为空，一个不为空，不对称
        if (left == null || right == null) {
            return false;
        }
        // 值不相等，不对称
        if (left.val != right.val) {
            return false;
        }
        // 递归检查：左子树的左孩子 vs 右子树的右孩子
        // 左子树的右孩子 vs 右子树的左孩子
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

// 方法二：迭代法
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            // 两个都为空，继续
            if (left == null && right == null) {
                continue;
            }
            // 一个为空或值不等
            if (left == null || right == null || left.val != right.val) {
                return false;
            }
            // 按对称顺序加入队列
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

Go 实现

// 方法一：递归法
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isMirror(root.Left, root.Right)
}

func isMirror(left, right *TreeNode) bool {
    // 两个都为空，对称
    if left == nil && right == nil {
        return true
    }
    // 一个为空，一个不为空，不对称
    if left == nil || right == nil {
        return false
    }
    // 值不相等，不对称
    if left.Val != right.Val {
        return false
    }
    // 递归检查对称位置
    return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}

// 方法二：迭代法
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    queue := []*TreeNode{root.Left, root.Right}
    for len(queue) > 0 {
        left := queue[0]
        right := queue[1]
        queue = queue[2:]
        // 两个都为空，继续
        if left == nil && right == nil {
            continue
        }
        // 一个为空或值不等
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }
        // 按对称顺序加入队列
        queue = append(queue, left.Left, right.Right, left.Right, right.Left)
    }
    return true
}

示例演示

示例 1 演示：[1,2,2,3,4,4,3]

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

递归调用过程：

1. isMirror(2, 2) → 值相等
2. isMirror(3, 3) → 值相等，且都为叶子节点 → true
3. isMirror(4, 4) → 值相等，且都为叶子节点 → true
4. 最终返回 true

示例 2 演示：[1,2,2,null,3,null,3]

  1
 / \
2   2
 \   \
  3   3

递归调用过程：

1. isMirror(2, 2) → 值相等
2. isMirror(null, null) → true（左子树的左 vs 右子树的右）
3. isMirror(3, 3) → 值相等
4. 但是结构上：左子树只有右孩子，右子树只有右孩子
5. 实际上在第二层比较时：left.left = null, right.right = null
6. left.right = 3, right.left = null → 返回 false

注意：示例 2 的关键在于右子树的左孩子是 null，而左子树的右孩子是 3

答案有效性证明

正确性证明

充分性证明：

如果算法返回 true，那么二叉树一定是对称的。

• 递归法确保了每个对称位置的节点值都相等
• 所有对应位置的结构都一致（同时为空或同时存在）

必要性证明：

如果二叉树是对称的，那么算法一定返回 true。

• 对称二叉树的定义就是左右子树互为镜像
• 算法正好按照镜像的定义进行验证

边界情况覆盖：

• 空树：返回 true
• 单节点：返回 true
• 完全不对称：正确返回 false
• 值相同但结构不同：正确返回 false

复杂度分析

时间复杂度：O(n)

• 需要访问树中的每个节点恰好一次
• n 为二叉树的节点总数

空间复杂度：

递归法：O(h)

• h 为树的高度
• 最坏情况（链状树）：O(n)
• 最好情况（完全平衡树）：O(log n)

迭代法：O(n)

• 队列最多存储一层的所有节点
• 最坏情况下（完全二叉树的最后一层）：约 n/2 个节点
• 因此空间复杂度为 O(n)

问题总结

关键要点

1. 对称的本质：左子树和右子树互为镜像
2. 递归思维：将大问题分解为相同的子问题
3. 边界处理：空节点的处理是关键
4. 对称配对：left.left ↔ right.right，left.right ↔ right.left

解题技巧

• 画图理解：对称问题一定要画图，直观理解对称关系
• 递归模板：树的对称、相同、翻转等问题都有相似的递归模式
• 测试用例：特别注意结构相同但值不同的情况，以及值相同但结构不同的情况

推荐方案

优先使用递归法，因为：

• 代码简洁易懂
• 空间效率更高（平均情况下）
• 符合树的天然递归结构

这个问题是理解二叉树递归操作的经典例题，掌握后可以轻松应对类似的树结构比较问题。