题解 | #树的子结构#

树的子结构

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

from pickle import NONE
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param pRoot1 TreeNode类 
# @param pRoot2 TreeNode类 
# @return bool布尔型
#
class Solution:
    def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        # write code here
        if pRoot1==None or pRoot2==None:
            return False
        if self.Judge(pRoot1,pRoot2):
            return True
        return self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)

    def Judge(self,root1,root2):
        # 1空2空为真  1空2不空为假  1不空2空为真  1不空2不空则继续判断左右部分
        if root1==None and root2==None:
            return True
        if root1==None and root2!=None:
            return False
        if root1 != None and root2==None:
            return True
        # 需要再判断一下根节点的值是不是相等
        if root1.val != root2.val:
            return False
        return self.Judge(root1.left,root2.left) and self.Judge(root1.right,root2.right)


  1. 主函数判断根节点的A树是否有B树结构,没有的话,递归判断A树的子树节点
  2. 用一个judge函数判断当前根节点的A树中是否包含子树B结构
  3. 主要注意点在于判断条件
剑指offer刷题笔记 文章被收录于专栏

24秋招剑指offer刷题的笔记

全部评论

相关推荐

06-27 18:53
门头沟学院 Java
这样才知道自己不适合搞代码,考公去咯
只爱喝白开水:我也发现不适合搞代码,打算转非技术方向了
点赞 评论 收藏
分享
06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务