文档章节

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

一贱书生
 一贱书生
发布于 2016/11/18 15:01
字数 870
阅读 42
收藏 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
博文 724
码字总数 600123
作品 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
LeetCode 98. Validate Binary Search Tree (有效二叉搜索树)

原题 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less ......

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

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

anycmd
2015/02/05
403
5

没有更多内容

加载失败,请刷新页面

加载更多

不用编写程序代码,送你一个爬虫程序批量采集猫眼电影票房数据

"大数据"是一个体量特别大,数据类别特别大的数据集,并且这样的数据集无法用传统数据库工具对其内容进行抓取、管理和处理。 "大数据"首先是指数据体量(volumes)大,指代大型数据集,一般在1...

技术阿飞
18分钟前
0
0
【Flutter教程】从零构建电商应用(一)

在这个系列中,我们将学习如何使用google的移动开发框架flutter创建一个电商应用。本文是flutter框架系列教程的第一部分,将学习如何安装Flutter开发环境并创建第一个Flutter应用,并学习Flu...

笔阁
39分钟前
5
0
什么是以太坊DAO?(三)

Decentralized Autonomous Organization,简称DAO,以太坊中重要的概念。一般翻译为去中心化的自治组织。 投票支付合约的所有费用和行动需要时间,并要求用户始终保持活跃,知情和专注。另一...

geek12345
41分钟前
2
0
一个本科学生对Linux的认知

一个本科学生对Linux的认知 我是一名大三的普通一本大学的软件工程的一名学生,学校开设了一些关于系统开发的课程,纸上得来终觉浅,学校的课程课时较短,想要在56个课时之内学会一些公司需要...

linuxCool
今天
3
0
CentOS 安装Tomcat

Tomcat 介绍 Tomcat是Apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 Java 程序写的网站用tomcat+jdk来运...

野雪球
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部