剑指 Offer 28. 对称的二叉树-轻识

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
/ \
2 2
\ \
3 3

示例 1：

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

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

题目解析

1. 树为对称树的情况：left 和 right 都为空，也就是父节点为叶子节点且相同

2. 树不为对称树的情况：

      1. not left and right      2. left and not right      3. left.val!=right.val

题目解答

代码展示

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def isSymmetric(self, root: TreeNode) -> bool:        '''            方法：广度优先搜索        '''        if not root:            return True         return self.bfs(root.left,root.right)
    # 方法：广度优先搜索    def bfs(self,left,right):        # step 1：left 和 right 都为空，        #         也就是父节点为叶子节点且相同        if not left and not right:            return True         # step 2：三种非对称树的情况：        #    1. not left and right        #    2. left and not right        #    3. left.val!=right.val        elif (not left and right) or (left and not right) or (left.val!=right.val):            return False
        return self.bfs(left.left,right.right) and self.bfs(left.right,right.left)

复杂度计算

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
-空间复杂度：O(N)，最差情况下（见下图），二叉树退化为链表，系统使用 O(N) 大小的栈空间。

运行结果