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

     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。

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