文档章节

海量数据:判断一棵树是否为另一棵树的子树

一贱书生
 一贱书生
发布于 2016/11/18 15:01
字数 870
阅读 10
收藏 0
点赞 0
评论 0

     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)。

  1. package Tree_Graph;  
  2.   
  3. import CtCILibrary.AssortedMethods;  
  4. import CtCILibrary.TreeNode;  
  5.   
  6. public class S4_8 {  
  7.   
  8.     // 判断t2是否是t1的子树  
  9.     public static boolean isSubTree(TreeNode t1, TreeNode t2) {  
  10.         if(t2 == null) {            // 空树始终是另一个树的子树  
  11.             return true;  
  12.         }  
  13.         if(t1 == null) {        // 此时r2非空,非空树不可能是一个空树的子树  
  14.             return false;  
  15.         }  
  16.         if(t1.data == t2.data) {            // 找到两树匹配  
  17.             if(isSameTree(t1, t2)){  
  18.                 return true;  
  19.             }  
  20.         }  
  21.           
  22.         // 继续在r1的左子树和右子树里找匹配  
  23.         return isSubTree(t1.left, t2) || isSubTree(t1.right, t2);  
  24.     }  
  25.       
  26.     // 判断两棵树是否相同  
  27.     public static boolean isSameTree(TreeNode t1, TreeNode t2) {  
  28.         if(t1==null && t2==null) {  
  29.             return true;  
  30.         }  
  31.         if(t1==null || t2==null) {  
  32.             return false;  
  33.         }  
  34.           
  35.         if(t1.data != t2.data) {  
  36.             return false;  
  37.         }  
  38.         return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);  
  39.     }  
  40.       
  41.     public static void main(String[] args) {  
  42.         // t2 is a subtree of t1  
  43.         int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};  
  44.         int[] array2 = {2, 4, 5, 8, 9, 10, 11};  
  45.   
  46.         TreeNode t1 = AssortedMethods.createTreeFromArray(array1);  
  47.         TreeNode t2 = AssortedMethods.createTreeFromArray(array2);  
  48.   
  49.         if (isSubTree(t1, t2))  
  50.             System.out.println("t2 is a subtree of t1");  
  51.         else  
  52.             System.out.println("t2 is not a subtree of t1");  
  53.   
  54.         // t4 is not a subtree of t3  
  55.         int[] array3 = {1, 2, 3};  
  56.         TreeNode t3 = AssortedMethods.createTreeFromArray(array1);  
  57.         TreeNode t4 = AssortedMethods.createTreeFromArray(array3);  
  58.   
  59.         if (isSubTree(t3, t4))  
  60.             System.out.println("t4 is a subtree of t3");  
  61.         else  
  62.             System.out.println("t4 is not a subtree of t3");  
  63.     }  
  64. }

 

 

 

对于上面讨论的2种解法,哪种解法比较好呢?其实有必要好好讨论一番:

1)方法一会占用O(N + M)的内存,而另外一种解法只会占用O(logN + logM)的内存(递归的栈内存)。当考虑scalability扩展性时,内存使用的多寡是个很重要的因素。

2)方法一的时间复杂度为O(N + M),方法二最差的时间复杂度是O(N*M)。所以要通过工程实践或者是历史数据看一下哪种方法更优。当然了,方法二也可能会很早发现两棵树的不同,早早的退出了checkSubTree。

总的来说,在空间使用上,方法二更好。在时间上,需要通过实际数据来验证。

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 723
码字总数 600072
作品 0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
leetcode:SameTree

题目要求(判断两个二叉数是否相等。): Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are struct......

wen_special
01/29
0
0
LeetCode-Same Tree

发布自Kindem的博客,欢迎大家转载,但是要注意注明出处 题目 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例...

Kindem
06/01
0
0
两个凡是:凡是在系统树上的才是有意义的,凡是脱离了树的都是无意义的。

我们的业务系统就类似一个小区(appSystem),一个小区中有很多资源,对小区中的所有资源按照类型进行树形的分类就是资源类型(resourceType),比如“停车位”是一种类型的资源、小区中的“...

anycmd
2015/02/05
398
5
【Qt笔记】使用 DOM 处理 XML

DOM 是由 W3C 提出的一种处理 XML 文档的标准接口。Qt 实现了 DOM Level 2 级别的不验证读写 XML 文档的方法。 与之前所说的流的方式不同,DOM 一次性读入整个 XML 文档,在内存中构造为一棵...

大道无名
2016/08/05
10
0
LeetCode:Symmetric Tree - 判断二叉树是否对称

1、题目名称 Symmetric Tree(判断二叉树是否对称) 2、题目地址 https://leetcode.com/problems/symmetric-tree/ 3、题目内容 英文:Given a binary tree, check whether it is a mirror o...

北风其凉
2015/08/13
0
0
[剑指offer] 树的子结构

题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 解题思路 递归思想,如果根节点相同则递归调用IsSubtree(),如果根节点不相同,则判断的左...

繁著
06/29
0
0
两棵树是否相同

原题   Given two binary trees, write a function to check if they are equal or not.   Two binary trees are considered equal if they are structurally identical and the nodes ......

一贱书生
2016/12/20
1
0
数据结构学习笔记(树、二叉树)

                       树(一对多的数据结构) 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树种: (1)有且仅有一个特定的称为根(Root)...

希希里之海
2017/05/15
0
0
xgboost的原理没你想像的那么难

xgboost 已然火爆机器学习圈,相信不少朋友都使用过。要想彻底掌握xgboost,就必须搞懂其内部的模型原理。这样才能将各个参数对应到模型内部,进而理解参数的含义,根据需要进行调参。本文的...

milter
2017/09/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

我的成长记录(一)

今天突然精神抖擞,在我的博客下新开一项分类>成长记录,专门记录每隔一段时间我的一点感悟吧。因为今天才专门花时间新开这样一个分类,所以以前有过的一些感悟没有记录下来,现在已经想不起...

dtqq
10分钟前
0
0
机器学习管理平台 MLFlow

最近工作很忙,博客一直都没有更新。抽时间给大家介绍一下Databrick开源的机器学习管理平台-MLFlow。 谈起Databrick,相信即使是不熟悉机器学习和大数据的工程湿们也都有所了解,它由Spark的...

naughty
今天
0
0
idea tomcat 远程调试

tomcat 配置 编辑文件${tomcat_home}/bin/catalina.sh,在文件开头添加如下代码。    CATALINA_OPTS="-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=7829" Idea端配......

qwfys
今天
1
0
遍历目录下的文件每250M打包一个文件

#!/usr/bin/env python # -*- utf-8 -*- # @Time : 2018/7/20 0020 下午 10:16 # @Author : 陈元 # @Email : abcmeabc@163.com # @file : tarFile.py import os import tarfile import thr......

寻爱的小草
今天
1
0
expect同步文件&expect指定host和要同步的文件&构建文件分发系统&批量远程执行命令

20.31 expect脚本同步文件 expect通过与rsync结合,可以在一台机器上把文件自动同步到多台机器上 编写脚本 [root@linux-5 ~]# cd /usr/local/sbin[root@linux-5 sbin]# vim 4.expect#!/...

影夜Linux
今天
1
0
SpringBoot | 第九章:Mybatis-plus的集成和使用

前言 本章节开始介绍数据访问方面的相关知识点。对于后端开发者而言,和数据库打交道是每天都在进行的,所以一个好用的ORM框架是很有必要的。目前,绝大部分公司都选择MyBatis框架作为底层数...

oKong
今天
13
0
win10 上安装解压版mysql

1.效果 2. 下载MySQL 压缩版 下载地址: https://downloads.mysql.com/archives/community/ 3. 配置 3.1 将下载的文件解压到合适的位置 我最终将myql文件 放在:D:\develop\mysql 最终放的位...

Lucky_Me
今天
2
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

问题终结者
今天
2
0
expect脚本同步文件expect脚本指定host和要同步的文件 构建文件分发系统批量远程执行命令

expect脚本同步文件 在一台机器上把文件同步到多台机器上 自动同步文件 vim 4.expect [root@yong-01 sbin]# vim 4.expect#!/usr/bin/expectset passwd "20655739"spawn rsync -av ro...

lyy549745
今天
1
0
36.rsync下 日志 screen

10.32/10.33 rsync通过服务同步 10.34 linux系统日志 10.35 screen工具 10.32/10.33 rsync通过服务同步: rsync还可以通过服务的方式同步。那需要开启一个服务,他的架构是cs架构,客户端服务...

王鑫linux
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部