101. 对称二叉树 - Symmetric Tree

🎯 问题描述（来源于LeetCode）

描述：
给你一个二叉树的根节点 root，检查它是否轴对称（即镜像对称）。

说明：

  • 轴对称意味着二叉树绕根节点中心对折后，左右两侧的节点值和结构完全一致。
  • 空树被认为是轴对称的。

示例：

  • 示例 1：
1
2
输入: root = [1,2,2,3,4,4,3]
输出: true
  • 示例 2：
1
2
输入: root = [1,2,2,null,3,null,3]
输出: false

💻 解题思路

思路1：递归镜像比较

算法步骤

  1. 处理根节点：

    • 如果根节点为空，直接返回 True（空树对称）。
    • 否则，调用辅助函数比较根节点的左子树和右子树是否镜像对称。

  2. 定义辅助函数

    • 输入两个节点 p 和 q，判断它们是否为镜像关系。
    • 递归出口：如果 p 或 q 有一个为 None，则只有当两者同时为 None 时才返回 True，否则 False。
    • 递归步骤：
      当前节点值相等 (p.val == q.val)
      并且 p 的左子树与 q 的右子树镜像对称
      并且 p 的右子树与 q 的左子树镜像对称。

  3. 返回结果：

    • isSymmetric 直接返回 isSameTree(root.left, root.right)。

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isMirror(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return q == p
        return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root.left is None or root.right is None:
            return root.left == root.right 
        return self.isMirror(root.left, root.right)

思路1：📊 性能分析

复杂度验证
  • 时间复杂度：O(n)O(n)，其中 nn 为二叉树的节点数。每个节点恰好被访问一次。
  • 空间复杂度：O(h)O(h)，其中 hh 为二叉树的高度。递归调用栈的深度最大为树的高度，最坏情况（链状）为 O(n)O(n)。

思考

  • 本题也可以用**迭代（队列/BFS）**实现：每次取出两个节点比较，然后按镜像顺序（左-右、右-左）入队。
  • 注意代码中 if root.left is None or root.right is None: return root.left == root.right 这一句可以简化。实际上当根节点非空时，直接调用 isSameTree 也能处理 None 的情况，因为 isSameTree 已经包含了判空逻辑。不过原代码这样写也能正确运行。
  • 对称二叉树是树相关问题的经典递归练习，理解“镜像比较”的递归结构对解决其他变形题（如翻转二叉树、判断子树等）很有帮助。