剑指 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) 大小的栈空间。
运行结果
评论