首页 > 试题广场 > 树的子结构
[编程题]树的子结构
  • 热度指数:780883 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
头像 牛客官方题解
发表于 2020-05-29 15:17:17
精华题解 描述 这是一篇针对初学者的题解。知识点:树,递归难度:二星 题解 题目抽象:给2棵树A,树B,判断B是否是A的子结构。子结构定义:树A和树B的根结点相等,并且树A的左子树和树B的左子树相等,树A的右子树和树B的右子树相等 方法:递归求解 第一步:根据题意可知,需要一个函数判断树A和树B是否有相同的 展开全文
头像 Jalr4ever
发表于 2019-08-26 01:33:23
赞数第一 由于写这篇文章的时候,牛客刚开的题解功能,我写的早,所以赞数第一,但明显质量挺不好,因为我是在 AC 的情况下写的题解,那时没有想很多,因为一般 AC 了,想法就是对的嘛 但坑爹的地方在于这道题的用例(其实牛客很多题也是。。。),牛客设计的不够健壮,所以其实我的想法是错误的 后期,Leet 展开全文
头像 超级大妖怪
发表于 2019-08-11 12:26:25
先写一个方法,传入两棵根节点值相同的树,判断tree1是否和tree2结构一样 public boolean doesTree1HasTree2(TreeNode tree1, TreeNode tree2){ if ( tree2 == null ){ return t 展开全文
头像 姚博vinson
发表于 2019-08-29 16:04:43
java代码,注释很清晰。 基本思路就是遍历大树,找到与子结构跟节点相同的节点,然后传入判断函数进行遍历比较 public class Solution {     //遍历大树   &n 展开全文
头像 秋招拿offer啊
发表于 2019-07-31 21:53:44
1.首先需要判断A,B的根节点是否一样。 2.如果不一样,判断A的左孩子和B的根节点是否一样,同理可判断A的右孩子和B的根节点是否一样。依次找下去 如果上述情况都不满足则说明不包含 1.如果找到了A中有值和B中的根节点相同,则比较左右子树是否相同。 2.如果B为空了,则说明包 展开全文
头像 ccจุ๊บ
发表于 2020-03-10 23:20:29
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None cl 展开全文
头像 心谭
发表于 2020-01-18 15:31:11
为了方便说明,先看两个例子。 例子 1 下图是第一个例子,可以看到 B 是 A 的子结构。 第一个例子的判断逻辑是: 比较当前节点值 递归比较左右节点的值 直到遍历完 B 树 例子 2 下图是第二个例子,可以看到 B 也是 A 的子结构。 但是 A 的根节点和 B 的根节点并不相同。因此对于 展开全文
头像 摇滚皮卡丘
发表于 2020-01-10 17:19:24
class Solution: def HasSubtree(self, s, t): def sametree(p,q): if p is None and q is None: return True 展开全文
头像 中工升达预备毕业生
发表于 2019-10-02 14:34:12
思路:第一步:在树A中找到和树B的节点一样的节点R第二部:判断树A以R为根节点的子树是不是包含树B一样的结构 摘自书上,思路很清晰了,做一个说明:第一步其实是对树A进行遍历,遍历的话,你可以选深度遍历,也可以选层次遍历,都ok// 刚开始写的层次遍历,感觉代码稍微有点长,就换成了深度遍历 publi 展开全文
头像 李可乐,
发表于 2020-03-29 21:33:12
    public boolean isSame(TreeNode root1, TreeNode root2){        &nbs 展开全文
头像 牛客最菜男人
发表于 2020-03-15 14:40:49
HasSubtree函数功能:排除题目约定,直接调用HasSubtree2函数 HasSubtree2函数功能:递归查找树root1中是否含有树root2结构 HasSubtree3函数功能:递归判断树root1是否是树root2的延申(包含两种情况:1.root1和root2完全相同;2.root 展开全文