首页 > 试题广场 >

树的子结构

[编程题]树的子结构
  • 热度指数：947840 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入两棵二叉树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
示例1

输入

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

输出

true
示例2

输入

{1,2,3,4,5},{2,4}

输出

true
示例3

输入

{1,2,3},{3,1}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 开车的阿Q
发表于 2021-07-18 15:52:52
精华题解 描述 这是一篇面对初级coder的题解。 知识点：链表 递归 DFS 难度：三星 题解 题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 考察树的基础知识与递归的思路，深度优先搜索。 方法一：递归求解 思路：双重递 展开全文
去ta的博客 赞 (23) 回复(1) 收起
头像 Maokt
发表于 2021-06-25 09:09:37
精华题解 算法思想一：递归 解题思路： 1.这道题判断是否是子结构，主要看pRoot2和pRoot1的根节点的值是否一样，一样的话再同时递归， 2.判断left节点，如果pRoot2的左节点为null,则说明pRoot2的left节点满足条件。 3.若pRoot2的节点不为null,并且pRoot 展开全文
去ta的博客 赞 (17) 回复(3) 收起
头像 牛客题解官
发表于 2022-04-25 18:10:26
精华题解 题目的主要信息： 给定两棵二叉树的层次遍历序列 判断二叉树B是否为A树的子树 我们约定空树不是任意一个树的子结构 举一反三： 学习完本题的思路你可以解决如下题目： JZ27. 二叉树的镜像 JZ28. 对称的二叉树 方法一：两层前序遍历（推荐使用） 知识点：二叉树递归 递归是一个过程或函数在其定 展开全文
去ta的博客 赞 (10) 回复(7) 收起
头像 大菠萝侦探
发表于 2021-07-01 00:45:38
精华题解 描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 基本思路 按照树 A 中每个节点的遍历顺序比较当前节点和 B 的根节点是否相同，如果相同就按照 B 的结构遍历他们的每个节点。例子是题目所给的样例： A : {8,8,#,9,#,2,#,5} B 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 超级大妖怪
发表于 2019-08-11 12:26:25
先写一个方法，传入两棵根节点值相同的树，判断tree1是否和tree2结构一样 public boolean doesTree1HasTree2(TreeNode tree1, TreeNode tree2){ if ( tree2 == null ){ return t 展开全文
去ta的博客 赞 (115) 回复(15) 收起
头像 姚博vinson
发表于 2019-08-29 16:04:43
java代码，注释很清晰。 基本思路就是遍历大树，找到与子结构跟节点相同的节点，然后传入判断函数进行遍历比较 public class Solution {     //遍历大树   &n 展开全文
去ta的博客 赞 (80) 回复(3) 收起
头像 心谭
发表于 2020-01-18 15:31:11
为了方便说明，先看两个例子。 例子 1 下图是第一个例子，可以看到 B 是 A 的子结构。 第一个例子的判断逻辑是： 比较当前节点值 递归比较左右节点的值 直到遍历完 B 树 例子 2 下图是第二个例子，可以看到 B 也是 A 的子结构。 但是 A 的根节点和 B 的根节点并不相同。因此对于 展开全文
去ta的博客 赞 (23) 回复(0) 收起
头像 橙子爱吃桃子
发表于 2020-05-08 19:12:00
C++/代码： class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if (!pRoot1 || !pRoot2) return false;//先判断空树返回false 展开全文
去ta的博客 赞 (15) 回复(0) 收起
头像 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 展开全文
去ta的博客 赞 (14) 回复(1) 收起
头像 头都大了
发表于 2020-03-10 09:34:43
首先：判断结构相同必须需要的函数 public boolean isSame(TreeNode root1,TreeNode root2){ if(root2 == null) return true; if(root1 == null) ret 展开全文
去ta的博客 赞 (14) 回复(2) 收起
头像 中工升达预备毕业生
发表于 2019-10-02 14:34:12
思路：第一步：在树A中找到和树B的节点一样的节点R第二部：判断树A以R为根节点的子树是不是包含树B一样的结构 摘自书上，思路很清晰了，做一个说明：第一步其实是对树A进行遍历，遍历的话，你可以选深度遍历，也可以选层次遍历，都ok// 刚开始写的层次遍历，感觉代码稍微有点长，就换成了深度遍历 publi 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 小陆要懂云
发表于 2021-08-18 14:52:39
先在树A中找到值为树B根节点的值的节点，然后判断这个节点的子树是否含有和树B一样的结构。 第一步中，查找与根节点值一样的节点，采用递归的方法来遍历树。 第二步中，同样采用递归的方法，判断判断当前对应节点是否相同，然后递归判断左、右节点，递归终止条件是到达了叶节点。 class Solution 展开全文
去ta的博客 赞 (8) 回复(2) 收起
头像 刘青松1
发表于 2022-03-02 21:56:44
递归方法判断子树 要判断B树是不是A的子树，就肯定要遍历A树的每一个节点 然后把A树的每一个节点当作根节点与B树进行比较-->进入子树判断方法 子树判断的三种情况：（当前节点） B树为空，说明B树遍历完毕,A树包含B树所有节点 -->true A树为空 (B树不为空)，说明B树有节点 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 阿宁6
发表于 2021-12-05 00:53:56
树的子结构 方法一：递归的方式（利用的是深度优先遍历的思想） public boolean isSame(TreeNode root1,TreeNode root2){ //如果root2为空，则为true（不需要考虑root1的状况） if(root2 == 展开全文
去ta的博客 赞 (5) 回复(0) 收起

问题信息

树 二叉树
难度：
1424条回答 169079浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号