输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
[编程题]树的子结构
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def judge(self, big, small): # 小的遍历完了，是True if not small: return True # 还没遍历完，大的没了，False if not big: return False # 俩都有，一样才能继续 if big.val == small.val: return self.judge(big.left, small.left) and self.judge(big.right, small.right) else: return False def DFS(self, big, small): # 到头了，返回False if not big: return False if big.val == small.val: res = self.judge(big, small) # 找到了，返回True if res: return True # 只要有一个是TRUE就返回 return self.DFS(big.left, small)&nbs***bsp;self.DFS(big.right, small) def HasSubtree(self, pRoot1, pRoot2): # write code here # 找到小树的根节点，然后遍历小树，看是不是一样 if not pRoot2: return False big = pRoot1 small = pRoot2 # 遍历大树 return self.DFS(big, small)
发表于 2021-07-04 10:16:45
回复(0)
def Issame(pRoot1, pRoot2): if pRoot2 is None: return True # 2还不为空 但1已经为空 if pRoot1 is None: return False if pRoot1.val != pRoot2.val: return False return Issame(pRoot1.left, pRoot2.left) and Issame(pRoot1.right, pRoot2.right) def HasSubtree(pRoot1, pRoot2): result = False if not (pRoot1 and pRoot2): return False if pRoot1.val == pRoot2.val: result = Issame(pRoot1, pRoot2) # 这个判断很巧妙 if not result: result = HasSubtree(pRoot1.left, pRoot2) or HasSubtree(pRoot1.right, pRoot2) # 只判断B是A的子树 return result感觉像这种在本地IDE调试好困难啊，这读取也太复杂了
编辑于 2021-06-19 11:35:24
回复(0)
# 参考了https://blog.csdn.net/qinian_ztc/article/details/104731375 的递归思想和判断标准
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
r = False
if pRoot1.val == pRoot2.val: # 进入子树匹配
r = self.HasSubtreeHelper(pRoot1, pRoot2)
if r is False: # 左子树的子树
r = self.HasSubtree(pRoot1.left, pRoot2)
if r is False: # 右子树的子树
r = self.HasSubtree(pRoot1.right, pRoot2)
return r
def HasSubtreeHelper(self, pRoot1, pRoot2):
if not pRoot2: # 父包含子
return True
if not pRoot1: # 子比父多
return False
if pRoot1.val <> pRoot2.val: # 节点不同
return False
return self.HasSubtreeHelper(pRoot1.left, pRoot2.left) and self.HasSubtreeHelper(pRoot1.right, pRoot2.right)
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
r = False
if pRoot1.val == pRoot2.val: # 进入子树匹配
r = self.HasSubtreeHelper(pRoot1, pRoot2)
if r is False: # 左子树的子树
r = self.HasSubtree(pRoot1.left, pRoot2)
if r is False: # 右子树的子树
r = self.HasSubtree(pRoot1.right, pRoot2)
return r
def HasSubtreeHelper(self, pRoot1, pRoot2):
if not pRoot2: # 父包含子
return True
if not pRoot1: # 子比父多
return False
if pRoot1.val <> pRoot2.val: # 节点不同
return False
return self.HasSubtreeHelper(pRoot1.left, pRoot2.left) and self.HasSubtreeHelper(pRoot1.right, pRoot2.right)
发表于 2021-04-19 23:07:51
回复(0)
class Solution: def HasSubtree(self,pRoot1,pRoot2): # 1.遍历A树 # A和B必须都不为空 if not pRoot1 and pRoot2: return None result = False if pRoot1 and pRoot2: # 找到A节点与B根节点相同的节点 if pRoot1.val == pRoot2.val: result = self.DoseTreeBIsTreeA(pRoot1,pRoot2) if not result: result = self.HasSubtree(pRoot1.left,pRoot2) if not result: result = self.HasSubtree(pRoot1.right,pRoot2) return result def DoseTreeBIsTreeA(self,pRootA,pRootB): # 2.确认B是否同A某一子节点相同 if not pRootB: return True if not pRootA: return False if pRootA != pRootB: return False return self.DoseTreeIsTreeA(pRootA.left,pRootB.left) and self.DoseTreeIsTreeA(pRootA.right,pRootB.right)
解法：暴力破解
递归遍历A树，找到值与B树根节点值相同的节点，然后通过另一个递归判断A、B树左右节点是否都相同
发表于 2021-04-12 16:35:18
回复(0)
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if pRoot1 is None&nbs***bsp;pRoot2 is None: return False if pRoot1.val == pRoot2.val: return self.ischild(pRoot1, pRoot2) \ &nbs***bsp;self.HasSubtree(pRoot1.left, pRoot2) \ &nbs***bsp;self.HasSubtree(pRoot1.right, pRoot2) def ischild(self, pRoot1, pRoot2): if pRoot2 is None: return True if pRoot1 is None: return False if pRoot1.val != pRoot2.val: return False return self.ischild(pRoot1.left, pRoot2.left) \ and self.ischild(pRoot1.right, pRoot2.right)
发表于 2021-01-08 21:05:48
回复(0)
def same(self, art, brt): #label = False if not brt: return True if art and art.val == brt.val: return self.same(art.left, brt.left) and self.same(art.right, brt.right) else: return False def HasSubtree(self, pRoot1, pRoot2): # write code here if (not pRoot2)&nbs***bsp;(not pRoot1): return False lable = None queue = [pRoot1] while len(queue)>0: p = queue.pop(0) lable = self.same(p, pRoot2) if lable: break else: if p.left: queue.append(p.left) if p.right: queue.append(p.right) return lable我是采用层次遍历，每一个节点跟子结构对比，这样的时间为O(nm),可能还有更好的解法吧，我是菜鸟。
发表于 2020-08-04 13:53:23
回复(0)
Python Solution
class Solution: def HasSubtree(self, pRoot1, pRoot2): if pRoot1==None&nbs***bsp;pRoot2==None:return False def back(pRoot1,pRoot2): if pRoot2 == None:return True if pRoot1==None:return False if pRoot1.val!=pRoot2.val: return False else:return back(pRoot1.left,pRoot2.left) and back(pRoot1.right,pRoot2.right) if back(pRoot1,pRoot2):return True else: return self.HasSubtree(pRoot1.left,pRoot2)&nbs***bsp;self.HasSubtree(pRoot1.right,pRoot2)
编辑于 2020-05-31 19:01:05
回复(0)
def judge(self,root,R):
if R is None: return True
if root is None: return False
if root.data is not R.data:return False
return self.judge(root.left,R.left) and self.judge(root.right,R.right)
def is_sub_structure(self,root,R):
if R is None:return False
if root is None:return False
s = []
s.append(root)
while s.__len__() is not 0:
t = s.pop(0)
if t.data is R.data:
result = self.judge(t,R)
if result:return True
else:
if t.left: s.append(t.left)
if t.right: s.append(t.right)
else:
if t.left: s.append(t.left)
if t.right: s.append(t.right)
return False
对一个python回答的修改
思路是：层次遍历，先找到第一个与需判断的树的根节点一致的节点，
若相同则进入判断是否为子结构的判断函数，真返回，假则继续遍历
编辑于 2020-03-29 18:22:42
回复(0)
## 本题的子结构应该只限于B的根节点是A的跟节点或左右节点的情况。否则情况会比较麻烦，一个比较笨的方法是遍历A的每一个节点作为子结构根， (1184)## 同B进行比较 class Solution: def HasSubtree(self, pRoot1, pRoot2): (1185)# write code here if pRoot2 == None&nbs***bsp;pRoot1 == None: return False return self.checkNode(pRoot1, pRoot2)&nbs***bsp;self.checkNode(pRoot1.left, pRoot2)&nbs***bsp;self.checkNode(pRoot1.right, pRoot2) def checkNode(self, pRoot1, pRoot2): if pRoot2 == None: return True if pRoot1 == None: return False if pRoot1.val != pRoot2.val: return False return self.checkNode(pRoot1.right, pRoot2.right) and self.checkNode(pRoot1.left, pRoot2.left)
发表于 2020-03-01 17:49:42
回复(0)
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def judge(self, p1: TreeNode, p2: TreeNode) -> bool:
if not p2:
return True
else:
if not p1 or p1.val != p2.val:
return False
return self.judge(p1.right, p2.right) and self.judge(p1.left, p2.left)
def HasSubtree(self, pRoot1, pRoot2):
if not pRoot1 or not pRoot2:
return False
else:
result = False
if pRoot1.val == pRoot2.val:
result = self.judge(pRoot1, pRoot2)
if not result:
result = self.HasSubtree(pRoot1.right, pRoot2)
if not result:
result = self.HasSubtree(pRoot1.left, pRoot2)
return result
p1 = TreeNode(1)
p1.left = TreeNode(2)
p1.right = TreeNode(3)
p2 = TreeNode(1)
p2.right = TreeNode(3)
s = Solution()
ans = s.HasSubtree(p1, p1)
print(ans)
编辑于 2020-02-27 20:25:33
回复(0)
首先说明没用递归，我真的搞不懂递归，希望可以帮到一样不太懂递归的同学：
用两个hashmap分别储存两个树，遍历子树的表检查当前根值是否一样
如果有子节点那就检查子节点是否一样
某一步不一样return False
全通过True
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
if not pRoot1&nbs***bsp;not pRoot2:return False
res1=self.preorderTraversal(pRoot1)
res2 =self.preorderTraversal(pRoot2)
for i in res2:
if not i in res1:
return False
elif res2[i].left and not res1[i].left&nbs***bsp;res2[i].left and res2[i].left.val != res1[i].left.val:
return False
elif res2[i].right and not res1[i].right&nbs***bsp;res2[i].right and res2[i].right.val != res1[i].right.val:
return False
return True
def preorderTraversal(self, root):
res = {} # store result
stack = [] # helper stack
cur = root # current node
while stack&nbs***bsp;cur:
while cur:
res[cur.val]=cur
stack.append(cur)
cur = cur.left
top = stack.pop()
cur = top.right
return res 我继续学递归去了。。。
发表于 2020-01-12 06:38:09
回复(0)
Python Solution:
我是不是麻烦了
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if pRoot1 == None&nbs***bsp;pRoot2 == None: return False def hasEqual(pRoot1, pRoot2): if pRoot2==None: return True if pRoot1==None: return False if pRoot1.val==pRoot2.val: if pRoot2.left == None: leftEqual=True else: leftEqual = hasEqual(pRoot1.left,pRoot2.left) if pRoot2.right==None: rightEqual=True else: rightEqual = hasEqual(pRoot1.right,pRoot2.right) return leftEqual and rightEqual return False if pRoot1.val==pRoot2.val: ret = hasEqual(pRoot1,pRoot2) if ret: return True ret = self.HasSubtree(pRoot1.left, pRoot2) if ret: return True ret = self.HasSubtree(pRoot1.right, pRoot2) return ret
发表于 2019-12-07 16:20:44
回复(0)
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here # 大嵌套里小嵌套 # 大嵌套是为了遍历proot1的点 # 小嵌套是为了比较当前proot1和proot2是否相似 if pRoot2==None: return False # 空集警告 if self.comu(pRoot1,pRoot2): return True elif pRoot1!=None: return self.HasSubtree(pRoot1.left,pRoot2)&nbs***bsp;self.HasSubtree(pRoot1.right,pRoot2) else: return False def comu(self, pRoot1, pRoot2): if pRoot2==None: #针对proot1与proot2一样深的情况 return True if pRoot1==None: #针对proot1比proot2深的情况，不写这一步下一步会有val值警告 return False if pRoot1.val==pRoot2.val: return self.comu(pRoot1.left,pRoot2.left) and self.comu(pRoot1.right,pRoot2.right) return False #针对proot1没有proot2深的情况
发表于 2019-12-06 21:52:35
回复(0)
class Solution: def compare(self,proot1,proot2): if proot2==None: return True if proot1==None: return False if proot1.val!=proot2.val: return False return self.compare(proot1.left,proot2.left) and self.compare(proot1.right,proot2.right) def HasSubtree(self, pRoot1, pRoot2): # write code here result=False if(pRoot1!=None and pRoot2!=None): if pRoot1.val==pRoot2.val: result=self.compare(pRoot1,pRoot2) if result==False: result=self.HasSubtree(pRoot1.left,pRoot2) if result==False: result=self.HasSubtree(pRoot1.right,pRoot2) return result 这个问题的重点就是先遍历树，找到与子树根节点相同的节点，进入第二步判断根相同的节点的左右子树 是否相同，如果不相同就返回上一步，接着递归遍历左右子树。需要注意的是第二步判断中，子树结束时返回真，因为 子树已经与主树全部匹配完了；主树遍历完则代表匹配不成功，因为主树都遍历完了，子树还没遍历完，则不是其子树。
发表于 2019-11-28 17:53:06
回复(0)
求问一下，直接前序遍历两个树，当 tree1 包含 tree2 的时候，是不是就可以把 tree2 认作 tree1 的子结构？ 我这样试了一下是 AC 的，但不知道思路是不是正确。求指教一下。
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def qianxu(self, root): l = [] if root is not None: l.append(root.val) l = l + self.qianxu(root.left) l = l + self.qianxu(root.right) return l def HasSubtree(self, pRoot1, pRoot2): # write code here if pRoot2 is None: return False pRoot1List = self.qianxu(pRoot1) pRoot2List = self.qianxu(pRoot2) pRoot1ListStr = ''.join([str(i) for i in pRoot1List]) pRoot2ListStr = ''.join([str(i) for i in pRoot2List]) if(pRoot2ListStr in pRoot1ListStr): return True return False
发表于 2019-11-25 00:28:55
回复(0)
定义一个子函数,判断一棵树是不是另外一颗树的子树
如果它们从第一个节点的位置到子树最后一个节点的位置的值完全相同,则满足条件
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here def is_subtree(pRoot1,pRoot2): if not pRoot2: return True if not pRoot1: return False return pRoot1.val==pRoot2.val and is_subtree(pRoot1.left,pRoot2.left) and is_subtree(pRoot1.right,pRoot2.right) if not pRoot1 or not pRoot2: return False return is_subtree(pRoot1,pRoot2) or self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)
发表于 2019-10-23 13:22:31
回复(0)
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if pRoot1 == None or pRoot2 == None: return False return self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2) or self.isSame(pRoot1,pRoot2) def isSame(self,p,q): if q == None : return True if p == None : return False return p.val == q.val and self.isSame(p.left,q.left) and self.isSame(p.right,q.right)
Hint:
在HasSubtree中的返回值使用or判断，从顶点、左树、右树分别判断是否存在子结构，有任一存在即为True；在isSame中的返回值使用and判断，要求：顶点相等，左孩子和右孩子分别对应相等
编辑于 2019-10-10 11:50:44
回复(0)
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if not pRoot1 or not pRoot2: return False return self.isSame(pRoot1,pRoot2) or self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2) def isSame(self,p,q): if not q: return True if not p: return False return p.val==q.val and self.isSame(p.left,q.left) and self.isSame(p.right,q.right)
发表于 2019-10-03 10:14:36
回复(0)
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if not pRoot2: return False result = False if pRoot1: if pRoot1.val == pRoot2.val: result = self.treeA_has_treeB(pRoot1, pRoot2) if not result: result = self.HasSubtree(pRoot1.left, pRoot2) if not result: result = self.HasSubtree(pRoot1.right, pRoot2) return result def treeA_has_treeB(self, A, B): if not B: return True if not A: return False if A.val != B.val: return False return self.treeA_has_treeB(A.left, B.left) and self.treeA_has_treeB(A.right, B.right)
发表于 2019-09-01 10:29:52
回复(0)
问题信息
难度：
74条回答
5374收藏
167925浏览
通过挑战的用户
查看代码-
2023-02-26 23:04:24 -
2022-10-16 13:46:24
-
2022-10-13 17:48:07 -
2022-09-17 23:57:56 -
2022-09-16 15:18:43
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
