Cracking the coding interview--Q4.7

Cracking the coding interview--Q4.7
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1
译文：
有两棵很大的二叉树：T1有上百万个结点，T2有上百个结点。写程序判断T2是否为T1的子树。

X.

我觉得这道题目意欲考察如何在二叉树中结点数量非常巨大的情况下进行快速的查找与匹配， 不过除了常规的暴力法，我暂时想不到什么高效的方法。暴力法就很简单了， 先在T1中找到T2的根结点，然后依次去匹配它们的左右子树即可。

这里要注意的一点是，T1中的结点可能包含多个与T2根结点的值相同的结点。因此， 在T1中查找T2的根结点时，如果找到与T2匹配的子树，则返回真值；否则，还要继续查找， 直到在T1中找到一棵匹配的子树或是T1中的结点都查找完毕。

bool match(Node* r1, Node* r2){
    if(r1 == NULL && r2 == NULL) return true;
    else if(r1 == NULL || r2 == NULL) return false;
    else if(r1->key != r2->key) return false;
    else return match(r1->lchild, r2->lchild) && match(r1->rchild, r2->rchild);
}
bool subtree(Node* r1, Node* r2){
    if(r1 == NULL) return false;
    else if(r1->key == r2->key){
        if(match(r1, r2)) return true;
    }
    else return subtree(r1->lchild, r2) || subtree(r1->rchild, r2);
}
bool contain_tree(Node* r1, Node* r2){
    if(r2 == NULL) return true;
    else return subtree(r1, r2);
}

X. http://blog.csdn.net/navyifanr/article/details/19234825
方法2：对T1,T2中的每个节点生成一个hash值，hash值由当前节点和左右子树共同决定；

1.     //对二叉树每个节点生成一个hash值  
2.     public static boolean method1(TreeNode tn1,TreeNode tn2){  
3.         hash(tn1);  
4.         hash(tn2);  
5.         HashSet<Integer> set=new HashSet<Integer>();  
6.         preTraverse(tn1,set);  
7.         if(set.contains(tn2.hashValue))  
8.             return true;  
9.         else  
10.             return false;  
11.     }  
12.     private static void preTraverse(TreeNode tn1,HashSet<Integer> set){  
13.         if(tn1==null) return;  
14.         set.add(tn1.hashValue);  
15.         preTraverse(tn1.lchild,set);  
16.         preTraverse(tn1.rchild,set);  
17.     }  
18.     private static int hash(TreeNode tnode){  
19.         if(tnode==null) return 0;  
20.         if(tnode.lchild==null&&tnode.rchild==null)  
21.             tnode.hashValue=tnode.value;  
22.         else  
23.             tnode.hashValue=3*tnode.value+5*hash(tnode.lchild)+7*hash(tnode.rchild);  
24.         return tnode.hashValue;  
25.     }  
26. 
    class TreeNode{  
27.     int value;  
28.     TreeNode lchild;  
29.     TreeNode rchild;  
30.     TreeNode parent;  
31.     int hashValue;  
32.       
33.     public static void insert(TreeNode tnode,int x,TreeNode p){  
34.         if(tnode==null){  
35.             tnode=new TreeNode();  
36.             tnode.value=x;  
37.             tnode.lchild=null;  
38.             tnode.rchild=null;  
39.             if(p.value>x)  
40.                 p.lchild=tnode;  
41.             else  
42.                 p.rchild=tnode;  
43.             tnode.parent=p;  
44.             return;  
45.         }  
46.           
47.         if(x<tnode.value){  
48.             insert(tnode.lchild,x,tnode);  
49.         }else{  
50.             insert(tnode.rchild,x,tnode);  
51.         }  
52.     }  
53.       
54.     public static TreeNode createBinaryTree(int[] values){  
55.         TreeNode root=new TreeNode();  
56.         root.value=values[0];  
57.         for(int i=1;i<values.length;i++){  
58.             insert(root,values[i],root);  
59.         }  
60.         return root;  
61.     }  
62. } 

X. http://blog.csdn.net/java_wliang/article/details/41217379

把T1，T2两颗树转换成字符串，如[head.data [左子树] [右子树]]，同时左右子树以相同的方法转换。

如果左子树或者右子树存在一颗并且只为一颗子树为空，则该子树设置为[null]，这样就能区分左子树或者右子树

然后判断T2是否为T1的子串即可。

1.     public static String tranceString(Node_4_6 node) {  
2.         if(node == null) {  
3.             return "[null]";  
4.         } else {  
5.             if(node.lchild!=null || node.rchild!=null) {  
6.                 return "[" + node.data + tranceString(node.lchild) + tranceString(node.rchild) + "]";  
7.             } else {  
8.                 return "[" + node.data + "]";  
9.             }  
10.         }  
11.     }  
12.     public static void main(String args[]) {  
13.         String pattern2 = tranceString(t2Parent);  
14.         System.out.println(pattern1.contains(pattern2));  
15.     } 

Read full article from Cracking the coding interview--Q4.7