题目
原文：
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的子树。
解答
我觉得这道题目意欲考察如何在二叉树中结点数量非常巨大的情况下进行快速的查找与匹配， 不过除了常规的暴力法，我暂时想不到什么高效的方法。暴力法就很简单了， 先在T1中找到T2的根结点，然后依次去匹配它们的左右子树即可。
这里要注意的一点是，T1中的结点可能包含多个与T2根结点的值相同的结点。因此， 在T1中查找T2的根结点时，如果找到与T2匹配的子树，则返回真值；否则，还要继续查找， 直到在T1中找到一棵匹配的子树或是T1中的结点都查找完毕。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
}
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 100;
struct Node{
int key;
Node *lchild, *rchild, *parent;
};
Node node[maxn];
int cnt;
void init(){
memset(node, '\0', sizeof(node));
cnt = 0;
}
void create_minimal_tree(Node* &head, Node *parent, int a[], int start, int end){
if(start <= end){
int mid = (start + end)>>1;
node[cnt].key = a[mid];
node[cnt].parent = parent;
head = &node[cnt++];
create_minimal_tree(head->lchild, head, a, start, mid-1);
create_minimal_tree(head->rchild, head, a, mid+1, end);
}
}
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);
}
int main(){
init();
int a1[] = {
0, 1, 2, 3, 4, 5, 6
};
int a2[] = {
0, 1, 2
};
Node *r1 = NULL, *r2 = NULL;
create_minimal_tree(r1, NULL, a1, 0, 6);
create_minimal_tree(r2, NULL, a2, 0, 2);
if(contain_tree(r1, r2))
cout<<"tree r1 contains r2"<<endl;
else cout<<"tree r1 does not contaions r2"<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2012/12/30/4.7/
