题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路
- 在大树中找到和小树根节点相同的节点。
- 然后以此节点为根节点，在大树上往下搜索对比小书左右节点是否相同，不同则返回false
- 如果2步中最后返回false 回到第一步，从大树的左子树找和小树根节点相同的节点。
- 如果3步中最后返回false 回到第一步，从大树的右子树找和小树根节点相同的节点。
代码实现
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
| struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL)
{}
};
class Tree
{
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool res = false;
if(pRoot1!=nullptr&&pRoot2!=nullptr)
{
if(pRoot1->val==pRoot2->val)
res = isSubtree(pRoot1, pRoot2);
if(!res)
res = HasSubtree(pRoot1->left, pRoot2);
if(!res)
res = HasSubtree(pRoot1->right, pRoot2);
}
return res;
}
bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2==nullptr)
return true;
if(pRoot1==nullptr)
return false;
if(pRoot1->val!=pRoot2->val)
return false;
return isSubtree(pRoot1->left, pRoot2->left) && isSubtree(pRoot1->right, pRoot2->right);
}
};
|
