题解 | #树的子结构#

树的子结构

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

python3,递归方法。
子结构内的递归:子结构,意味着从头到子树递归的匹配上。
    如果子结构递归到空,即意味着完成了全部匹配,返回True。如果子结构没递归到空且这时树递归到空了,即意味着不够匹配,返回False;或者结点不相等,匹配失败,返回False。
子结构头的递归:如果以当前树结点作为子结构的头,匹配不上,这个头也要在树内递归的变化。
    如果子结构是空树,直接返回False,如果子结构的头(树结点)是空,不够匹配,返回False。如果树当前结点作为头,递归成功,则返回True;或者换头之后匹配成功,也返回True,用or连接这个递归。
class Solution:
    # 头本身也要递归
    def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        def dfs(h1, h2): # 从头递归判断
            if not h2: return True
            if not h1 or h1.val != h2.val: return False
            return dfs(h1.left, h2.left) and dfs(h1.right, h2.right)
            
        return bool(pRoot1 and pRoot2) and (dfs(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2))


全部评论

相关推荐

06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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