day23-2022.11.19
题目信息来源
作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源:力扣(LeetCode)
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3/ \4 5/ \1 2
给定的树 B:
4 /1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
输入:A = [1,2,3], B = [3,1]
输出:false输入:A = [3,4,5,1,2], B = [4,1]
输出:true
限制:0 <= 节点个数 <= 10000
题解:个人版,队列方法
可能是广度遍历的方法。我的代码可以看到有很多重复,结构相似的代码段,之后看看题解考虑一下怎么优化。现在先考虑能不能用递归的方式
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if not B:return False # 空树不是任何树的子结构# 考虑了一下,可能是三个队列,一个是A的所有节点队列遍历,一个是B的所有队列,一个是检查A的时候单独的队列aQueue = [A]check_sub = Falsewhile aQueue:# 检查a队列有无和b队列对上的aNode = aQueue.pop(0)# 如果对不上考虑下一个节点if aNode.left!=None:aQueue.append(aNode.left)if aNode.right!=None:aQueue.append(aNode.right)# 如果对上,就需要检查结构,遍历b的结构if aNode.val==B.val:# 初始化b的遍历结构和a对应的子结构aSub, bSub = [aNode], [B]while bSub:a_node, b_node = aSub.pop(0), bSub.pop(0)# 如果pop的值相等,则可以考虑看看树的下一层的情况if b_node.val==a_node.val:# left都不为空,暂时结构上是正确的if b_node.left!=None and a_node.left!=None:bSub.append(b_node.left)aSub.append(a_node.left)check_sub = True# b不为空,a为空结构上错误elif b_node.left!=None and a_node.left==None:check_sub = Falsebreak# a和b都为空,结构上是正确的。# 其实还有一种情况:b为空,a不为空,这个我也不知道怎么处理其实,但似乎测试里没有这种情况,或者就是Falseelif b_node.left==None:check_sub = Trueif b_node.right!=None and a_node.right!=None:bSub.append(b_node.right)aSub.append(a_node.right)check_sub = Trueelif b_node.right!=None and a_node.right==None:check_sub = Falsebreakelif b_node.right==None:check_sub = Trueelse:check_sub = Falsebreakreturn check_sub
题解:个人方法,递归版本
这个很像之前的【矩阵中的路径】那道题,就是数据结构变了一下,如果广度就要两层遍历,深度就需要一层遍历加递归。
这里官方题解的解释更清楚,为啥需要两层遍历:
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dsbng/
若树 B 是树 A 的子结构,则子结构的根节点可能为树 A 的任意一个节点。因此,判断树 B 是否是树 A 的子结构,需完成以下两步工作:
- 先序遍历树 A 中的每个节点 nAn_AnA ;(对应函数
isSubStructure(A, B)
)- 判断树 A 中 以 nAn_AnA 为根节点的子树 是否包含树 B 。(对应函数
recur(A, B)
)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if not B:return False # 空树不是任何树的子结构# 递归参数:A和B的left或者right Node# 递归获得参数有多少种可能性,分别返回什么参数。首先希望传递的参数是出现子树可能性的时候的递归def checkSubTree(a_node, b_node):# 检查 aNode 的值和 bNode 的值是否相等if a_node==None and b_node!=None:return Falseelif b_node==None:return Trueif a_node.val!=b_node.val:return Falsereturn checkSubTree(a_node.left, b_node.left) and checkSubTree(a_node.right, b_node.right)aQueue = [A]while aQueue:# 检查a队列有无和b队列对上的aNode = aQueue.pop(0)# 如果对不上考虑下一个节点if aNode.left!=None:aQueue.append(aNode.left)if aNode.right!=None:aQueue.append(aNode.right)# 如果对上,就需要检查结构,遍历b的结构if aNode.val==B.val:check_sub = checkSubTree(aNode.right, B.right) and checkSubTree(aNode.left, B.left) if check_sub==True:return Trueelse:continuereturn False
看到最后官方题解是基于递归版本,在第一层遍历部分,用来递归来解决。
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dsbng/
返回值: 若树 B 是树 A 的子结构,则必满足以下三种情况之一,因此用或 || 连接;
- 以 节点 A 为根节点的子树 包含树 B ,对应
recur(A, B)
;- 树 B 是 树 A 左子树 的子结构,对应
isSubStructure(A.left, B)
;- 树 B 是 树 A 右子树 的子结构,对应
isSubStructure(A.right, B)
;
可以尝试在我的基础上从这个思路上优化,但特殊情况我可能现在提前 return
,需要注意的是,这里还要加入 not A
,中间是 or
连接。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if not B or not A:return False # 空树不是任何树的子结构# 递归参数:A和B的left或者right Node# 递归获得参数有多少种可能性,分别返回什么参数。首先希望传递的参数是出现子树可能性的时候的递归def checkSubTree(a_node, b_node):# 检查 aNode 的值和 bNode 的值是否相等if a_node==None and b_node!=None:return Falseelif b_node==None:return Trueif a_node.val!=b_node.val:return Falsereturn checkSubTree(a_node.left, b_node.left) and checkSubTree(a_node.right, b_node.right)return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B) or checkSubTree(A, B)