【剑指Offer】18树的子结构

骑猪看日落 2022-05-05 04:27 172阅读 0赞

## 题目描述 ##

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

时间限制：1秒；空间限制：32768K

## 解题思路 ##

解题思路分为两步，主要用到了递归的方法。第一步先遍历树A，找到和树B根节点值相同的节点A'；第二步判断以A'为根节点的子树中是否包含树B。

# -*- 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
            result = False
            if pRoot1!=None and pRoot2!=None:
                if pRoot1.val == pRoot2.val:
                    result = self.iscomprise(pRoot1,pRoot2) #不写self.会报错
                if result != True:
                    result = self.HasSubtree(pRoot1.left,pRoot2)
                if result != True:
                    result = self.HasSubtree(pRoot1.right,pRoot2)
            return result
        
        def iscomprise(self, pRoot1, pRoot2):
            if pRoot2 == None:
                return True
            if pRoot1 == None:
                return False
            if pRoot1.val == pRoot2.val:
                return self.iscomprise(pRoot1.left, pRoot2.left) and self.iscomprise(pRoot1.right, pRoot2.right)

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer-Java版】18树的子结构

树的子结构：输入两棵二叉树A B，判断B是不是A的子结构就是一个递归加上一个树的先序遍历 public class _Q18 { pub

素颜马尾好姑娘i/ 2022年08月21日 08:58/ 0 赞/ 123 阅读

相关剑指offer_面试题18_树的子结构

题目：输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。两个步骤： 1、第一步在树 A 中找到和树 B 的根结点的值一样的结点 R 2、第二步再判断树 A 中

我就是我/ 2022年08月04日 00:46/ 0 赞/ 141 阅读

相关剑指offer-题18：树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）实验平台：[牛客网][Link 1] -------------

╰+攻爆jí腚メ/ 2022年05月29日 00:56/ 0 赞/ 164 阅读

相关剑指Offer-树的子结构

这道题题目的思路总结： 1）二叉树B当前节点值等于二叉树A当时节点值，则递归地去匹配B的左子树和A的左子树，B的右子树和A的右子树 2）二叉树B当前节点值不等于二叉树A

╰+哭是因爲堅強的太久メ/ 2022年05月22日 23:36/ 0 赞/ 166 阅读

相关【剑指Offer】18树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）时间限制：1秒；空间限制：32768K 解题思路解题思路

骑猪看日落/ 2022年05月05日 04:27/ 0 赞/ 173 阅读

相关【剑指offer】树的子结构

树的子结构题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） AC代码方法一 /

一时失言乱红尘/ 2022年04月10日 04:20/ 0 赞/ 147 阅读

相关【剑指Offer】（树）树的子结构

题目链接：[https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11

一时失言乱红尘/ 2022年03月16日 00:57/ 0 赞/ 160 阅读

相关 18. 树的子结构《剑指Offer》(Java版)

[github][] 题目描述 > 输入两棵二叉树A，B，判断B是不是A的子结构。 > > （ps：我们约定空树不是任意一个树的子结构） /

Bertha 。/ 2022年03月10日 13:54/ 0 赞/ 152 阅读

相关剑指Offer-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）解题思路：看到树，第一个想法就是肯定会用到递归。判断B是不是A的子

冷不防/ 2022年02月26日 02:24/ 0 赞/ 187 阅读

相关剑指offer-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）算法实现本博客没有写实现思想，但是在算法实现中已经用注释的

客官°小女子只卖身不卖艺/ 2022年02月13日 15:01/ 0 赞/ 211 阅读