面试题18:树的子结构

题目:输入两颗二叉树A和B,判断B是不是A的子结构。二叉树的节点定义如下:

1
2
3
4
5
6
7
struct BinaryTreeNode{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
{}
};


分析

要判断B是不是A的子结构,也就是要判断B是不是 A的子树。我们可以先遍历A,如果某一个S节点的value和B树的根节点相同,就判断S和B的左右子树是否相等,如果相等,B就是A的子结构;否则跳过S继续建立A,直到遍历完成。

代码如下:

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
bool HasSubTree(BinaryTreeNode* root1,BinaryTreeNode* root2)
{
if(root1==NULL)
{
if(root2==NULL)
return true;
else
return false;
}
if(root2==NULL)
return true;
if(root1->value==root2->value)
{
if(HasSubTree(root1->left,root2->left) &&
HasSubTree(root1->right,root2->right))
{
return true;
}
else
{
if(HasSubTree(root1->left,root2) || HasSubTree(root1->right,root2))
{
return true;
}
else
{
return false;
}
}
}
else
{
if(HasSubTree(root1->left,root2) || HasSubTree(root1->right,root2))
{
return true;
}
else
{
return false;
}
}
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往