T1是一棵含有几百万个节点的树,T2含有几百个节点。判断T2是否是T1 的子树。
首先考虑小数据量的情况,可以根据树的前序和中序遍历所得的字符串,来通过判断T2生成的字符串是否是T1字符串的子串,来判断T2是否是T1的子树。假设T1的节点数为N,T2的节点数为M。遍历两棵树算法时间复杂性是O(N + M), 判断字符串是否为另一个字符串的子串的复杂性也是O( N + M)(比如使用KMP算法)。所需要的空间也是O(N + M)。
这里有一个问题需要注意:对于左节点或者右节点为null的情况,需要在字符串中插入特殊字符表示。否则对于下面这种情形将会判断错误:
因此如果插入特殊字符,上述两棵树的中序和前序遍历的结果是相同的。
由于本例有几百万的节点,需要占用O(N + M)的内存。
如果换一种思路,就是遍历T1,每当T1的某个节点与T2的根节点值相同时,就判断两棵子树是否相同。这个算法的复杂度是O(N*M)。我们再仔细思考一下。因为只有在节点值与T2的根节点值相同才会调用O(M)。假设有K次这种情况,那么算法的复杂度就是O(N + K*M)。下面是代码实现:
struct TreeNode{
TreeNode *leftChild;
TreeNode *rightChild;
int data;
};
// check sub tree n1 == sub tree n2
bool checkSubTree(const TreeNode* n1, const TreeNode* n2){
if( n1 == nullptr && n2 == nullptr )
return true;
if( n1 == nullptr || n2 == nullptr )
return false;
if( n1->data != n2->data )
return false;
return checkSubTree(n1->leftChild, n2->leftChild) && checkSubTree(n1->rightChild, n2->rightChild);
}
bool subTree(const TreeNode *n1, const TreeNode *n2){
if( n1 == nullptr){
return false; // the bigger tree is empty, so t2 is not subtree of t1
}
if( n1->data == n2->data){
if( checkSubTree(n1, n2))
return true;
}
return subTree(n1->leftChild, n2) || subTree(n2->rightChild, n2);
}
对于上面讨论的2种解法,哪种解法比较好呢?其实有必要好好讨论一番:
1)方法一会占用O(N + M)的内存,而另外一种解法只会占用O(logN + logM)的内存(递归的栈内存)。当考虑scalability扩展性时,内存使用的多寡是个很重要的因素。
2)方法一的时间复杂度为O(N + M),方法二最差的时间复杂度是O(N*M)。所以要通过工程实践或者是历史数据看一下哪种方法更优。当然了,方法二也可能会很早发现两棵树的不同,早早的退出了checkSubTree。
总的来说,在空间使用上,方法二更好。在时间上,需要通过实际数据来验证。
分享到:
相关推荐
海量数据:海量数据2020年年度报告.PDF
海量数据:海量数据2021年半年度报告.PDF
"海量数据:首次公开发行股票招股说明书.PDF" 本资源摘要信息是关于北京海量数据技术股份有限公司(以下简称“公司”)首次公开发行股票的招股说明书。该说明书旨在为投资者提供公司的基本情况、业务概况、财务状况...
海量数据:2019年半年度报告.PDF
海量数据处理:十道面试题与十个海量数据处理方法总结
海量数据是发展趋势,对数据分析和挖掘也越来越重要,从海量数据中提取有用信息重要而紧迫,这便要求处理要准确,精度要高,而且处理时间要短,得到有价值信息要快,所以,对海量数据的研究很有前途,也很值得进行...
海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化...
从海量素剧中查找中位数,从海量数据中查找一个数,海量数据问题
海量数据处理的大杀器:腾讯分布式数据仓库 阿里技术嘉年华
海量数据 海量数据 海量数据
海量数据分析:Sawzall并行处理
西电海量数据管理大作业,有图,有设计思路
hadoop海量数据处理技术详解,包括hdfs、MapReduce、hive、sqoop等相关技术和伪代码,代码是使用python语言写的。
《深入搜索引擎:海量信息的压缩、索引和查询》作为斯坦福大学信息检索课程的教材之一,具有一定的阅读难度,主要面向信息检索专业高年级本科生和研究生、搜索引擎业界的专业技术人员和从事海量数据处理相关专业的...
这里提出了一种基于分布式计算技术进行管理和存储海量海洋科学数据方法,构建了海量海洋科学数据存储平台解决方案,采用Linux集群技术,设计开发一个基于Hadoop的海量数据存储平台.系统由五大模块组成,有系统管理模块、...
文件系统技术内幕:大数据时代海量数据存储之道.docx
基于openlayers和canvas绘制海量数据的实现
Java海量数据分页Bean, 适用于Oracle(适当修改,适用于任何... 注:此为3.0版,有清晰的注释,你可以看到笔者怎样将其一步步优化为适用于海量数据的分布Bean。目前用于20万条数据记录的分页,健步如飞,未见任何异常。
下面的方法是我对海量数据的处理方法进行了一个一般性的总结, 当然这些方法可能并不能 完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。 下面的一 些问题基本直接来源于公司的面试笔试题目...
● 海量数据分库分表+文件存储:Mysql8.0+ShardingSphere多维度分库分表 + 阿里云OSS ● 实时计算+数据处理+存储可视化:Flink1.13 + ClickHouse + HDFS + 数据清洗分层 + Echart可视化数据 ● 分布式链路追踪+监控+...