首页 > 试题广场 >

判断t1树中是否有与t2树完全相同的子树

[编程题]判断t1树中是否有与t2树完全相同的子树
  • 热度指数：19529 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

子树指一棵树的某个节点的全部后继节点

数据范围：树的节点数满足 ，树上每个节点的值一定在32位整型范围内
进阶：空间复杂度: ，时间复杂度
示例1

输入

{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}

输出

true

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 LaN666
发表于 2021-08-08 23:45:48
题目描述: 简单来说，这道题目就是要判断t1树中是否包含t2树。即t2是否为t1树的子树 方法一：递归要判断t2是否为t1的子树，那么就先在t1中找到t2的根节点，然后再进行遍历判断从当前节点的左右子树相不相同，如果一旦出现不同，那么立即返回false。如果t2遍历完节点，t1也遍历完节点，则证明t 展开全文
去ta的博客 赞 (8) 回复(2) 收起
头像 LifelongCode
发表于 2020-12-30 13:17:44
方法1：递归时间复杂度:O ( M ∗ N )当root1什么都没有的时候，在root1里面找不到任何节点直接返回false。当root2提前终止了，此时还没有遇到不符合root1树的节点，直接返回true。 public boolean isContains (TreeNode root1 展开全文
去ta的博客 赞 (6) 回复(2) 收起
头像 牛客82035003号
发表于 2022-03-27 21:33:52
//1.若树2为空，那么无论树1是否为空，树2都是树1的子树，返回true //2.若树2不为空，而树1为空，那么树2不可能是树1的子树，返回false //3.在树1树2都不为空的时候，就分三种情况， // 要么两棵树完全一样，用 issame(root1, root2)判断 // 要么树2属 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 诗云panther
发表于 2021-08-13 17:17:33
/**  * struct TreeNode {  *    int val;  *    struct TreeNode *left;  *    struct TreeNode *right; & 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 姐姐的遮阳伞
发表于 2022-03-23 01:26:45
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Sol 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 LourisXu
发表于 2021-08-12 16:34:30
递归容我骂两句，智障拓扑结构完全相同需要值也相同？？？ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Soluti 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 小陆要懂云
发表于 2021-09-04 15:16:58
class Solution { bool isEqual(TreeNode* root1, TreeNode* root2){ if(!root1 && !root2) return true; if(!root1 || !root2) re 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-07-18 20:34:00
思路： 题目的主要信息： t1中含有t2的拓扑结构，即t2是t1的子树 方法一：先序递归法 具体做法： 对t1的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是t1与t2同步先序遍历，遍历完一个t2或者有不相等的结点为止。 class Solution 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 君鸿
发表于 2025-01-07 15:11:09
递归思路看到题目很容易想到用递归去求解。1、递归终止条件：如果root1和root2都为nullptr，则返回true。两者中一个为nullptr，一个不为nullptr，则返回false。2、如果root1和root2的val相同，则递归判断root1的左子树是否包含root2的左子树，同时roo 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 刷了100道题的亚瑟很喜欢溜溜球
发表于 2024-12-15 20:42:54
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
46条回答 4929浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断t1树中是否有与t2树完全相同的子树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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