101. 对称二叉树

Posted on Edited on In Views: Word count in article: 438 Reading time ≈ 1 mins.

101. 对称二叉树

题目链接：101. 对称二叉树

题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

核心思考：镜像对称比较

判断一棵树是否是对称二叉树，本质上是判断它的 左子树 和 右子树 是否互为“镜像”。这就要求两个子树：

  1. 头节点的值必须相等。
  2. 左子树的左节点和右子树的右节点对称。
  3. 左子树的右节点和右子树的左节点对称。

我们依然可以使用深度优先搜索 (DFS) 递归地同步遍历两棵树：

  • 递归出口：
    • 如果左右节点都为空，则是对称的（返回 True）。
    • 如果只有一个为空，或者两个都不为空但值不相等，则是不对称的（返回 False）。
  • 递归逻辑：继续深入比较，把 左树的左 与 右树的右 绑定比较，把 左树的右 与 右树的左 绑定比较。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(left_tree, right_tree):
            if not left_tree and not right_tree:
                return True
            if not (left_tree and right_tree) or left_tree.val != right_tree.val:
                return False
            # 镜像比较
            return dfs(left_tree.left, right_tree.right) and dfs(left_tree.right, right_tree.left)

        if not root:
            return True
        return dfs(root.left, root.right)

复杂度分析

  • 时间复杂度：O(N)，其中 N 是树的节点数。在最坏情况下，整个树的节点都会被深度优先搜索访问一次。
  • 空间复杂度：O(H)，其中 H 是树的高度。取决于递归调用栈的深度。对于高度平衡的二叉树，空间是 O(log N)；如果树呈线性退化，最坏需要占用 O(N) 的空间。