LeetCode 101. 对称二叉树

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归（推荐）
2. 解法二：迭代（BFS 成对入队）
相似题目

题目描述

✅ 101. 对称二叉树

思路分析

解法一：递归（推荐）

核心思路：

对称的本质是根节点的左子树与右子树互为镜像——即「外侧一对」和「内侧一对」同时对称。

定义辅助函数 isMirror(p, q)，判断以 p 和 q 为根的两棵子树是否互为镜像：

p == nil && q == nil → true（两者同时为空，对称）

p == nil || q == nil → false（一个为空另一个不为空，不对称）

p.val != q.val → false（值不同，不对称）

递归：isMirror(p.left, q.right) && isMirror(p.right, q.left)

外侧对：p 的左子树 vs q 的右子树

内侧对：p 的右子树 vs q 的左子树

与 100 题（相同的树）的对比：100 题是同侧比较，101 题是交叉比较。

复杂度分析：

时间复杂度：O(n)，其中 n 为树的节点总数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归调用栈深度；最坏情况（链式树）退化为 O(n)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    // 判断两棵子树是否互为镜像
    private boolean isMirror(TreeNode p, TreeNode q) {
        // 两者同时为空，对称
        if (p == null && q == null) {
            return true;
        }
        // 一个为空另一个不为空，不对称
        if (p == null || q == null) {
            return false;
        }
        // 当前节点值不同，不对称
        if (p.val != q.val) {
            return false;
        }
        // 交叉递归：外侧对 + 内侧对同时满足才对称
        return isMirror(p.left, q.right) && isMirror(p.right, q.left);
    }
}

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    // 判断两棵子树是否互为镜像
    var isMirror func(p, q *TreeNode) bool
    isMirror = func(p, q *TreeNode) bool {
        // 两者同时为空，对称
        if p == nil && q == nil {
            return true
        }
        // 一个为空另一个不为空，不对称
        if p == nil || q == nil {
            return false
        }
        // 当前节点值不同，不对称
        if p.Val != q.Val {
            return false
        }
        // 交叉递归：外侧对 + 内侧对同时满足才对称
        return isMirror(p.Left, q.Right) && isMirror(p.Right, q.Left)
    }
    return isMirror(root.Left, root.Right)
}

解法二：迭代（BFS 成对入队）

核心思路：

用队列模拟递归的过程，将需要比较的节点成对入队：

初始将 root.left 和 root.right 成对入队

每次从队列中取出两个节点 t1、t2 进行比较

若值相等，按镜像顺序将 (t1.left, t2.right) 和 (t1.right, t2.left) 成对入队

任意时刻值不相等则返回 false

复杂度分析：

时间复杂度：O(n)，其中 n 为树的节点总数，每个节点恰好访问一次

空间复杂度：O(n)，其中 n 为树的节点总数，队列最多同时存储 n 个节点

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 t1 = queue.poll();
            TreeNode t2 = queue.poll();

            // 两者同时为空，继续
            if (t1 == null && t2 == null) {
                continue;
            }
            // 一个为空或值不同，不对称
            if (t1 == null || t2 == null || t1.val != t2.val) {
                return false;
            }
            // 按镜像顺序将子节点成对入队
            queue.offer(t1.left);
            queue.offer(t2.right);
            queue.offer(t1.right);
            queue.offer(t2.left);
        }

        return true;
    }
}

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }

    // 成对入队，每次取出两个节点进行镜像比较
    queue := []*TreeNode{root.Left, root.Right}

    for len(queue) > 0 {
        t1 := queue[0]
        t2 := queue[1]
        queue = queue[2:]

        // 两者同时为空，继续
        if t1 == nil && t2 == nil {
            continue
        }
        // 一个为空或值不同，不对称
        if t1 == nil || t2 == nil || t1.Val != t2.Val {
            return false
        }
        // 按镜像顺序将子节点成对入队
        queue = append(queue, t1.Left, t2.Right, t1.Right, t2.Left)
    }

    return true
}

相似题目

题目	难度	考察点
100. 相同的树	简单	递归、DFS
104. 二叉树的最大深度	简单	递归、DFS
226. 翻转二叉树	简单	递归
572. 另一棵树的子树	中等	递归、DFS
110. 平衡二叉树	简单	递归、DFS
111. 二叉树的最小深度	简单	BFS、DFS
617. 合并二叉树	简单	递归
112. 路径总和	简单	DFS
543. 二叉树的直径	简单	DFS
222. 完全二叉树的节点个数	中等	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/52259577