文档章节

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

一贱书生
 一贱书生
发布于 2016/11/18 15:01
字数 870
阅读 17
收藏 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 二叉树解题报告

1. Binary Tree Preorder Traversal Description Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Analy......

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

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

anycmd
2015/02/05
398
5

没有更多内容

加载失败,请刷新页面

加载更多

面向对象类之间的关系

面向对象类之间的关系:is-a、has-a、use-a is-a关系也叫继承或泛化,比如大雁和鸟类之间的关系就是继承。 has-a关系称为关联关系,例如企鹅在气候寒冷的地方生活,“企鹅”和“气候”就是关...

gackey
21分钟前
0
0
读书(附电子书)|小狗钱钱之白色的拉布拉多

关注公众号,在公众号中回复“小狗钱钱”可免费获得电子书。 一、背景 之前写了一篇文章 《小狗钱钱》 理财小白应该读的一本书,那时候我才看那本书,现在看了一大半了,发现这本书确实不错,...

tiankonguse
44分钟前
0
0
Permissions 0777 for ‘***’ are too open

异常显示: @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: UNPROTECTED PRIVATE KEY FILE! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ......

李玉长
46分钟前
0
0
区块链10年了,还未落地,它失败了吗?

导读 几乎每个人,甚至是对通证持怀疑态度的人,都对区块链的技术有积极的看法,因为它有可能改变世界。然而,区块链技术问世已经10年了,我们仍然没有真正的用上区块链技术。 几乎每个人,甚...

问题终结者
今天
2
0
20180921 su与sudo命令、限制root用户通过ssh远程登录

su 命令 用户切换。 su # 切换到root用户su username # 切换到username用户# su 后面加-时,会初始化当前用户的各种环境su - username # 指定用户执行某些命令 su - -c "touch /tm...

野雪球
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部