剑指 Offer 28. 对称的二叉树

DayNightStudy

共 1510字,需浏览 4分钟

 ·

2021-01-30 23:11


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


例如,二叉树 [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) 大小的栈空间。

运行结果








浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报