1 题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
2 思路和方法
（1）先在A中找和B的根节点相同的结点
（2）找到之后遍历对应位置的其他结点，直到B中结点遍历完，都相同时，则B是A的子树
（3）对应位置的结点不相同时，退出继续在A中寻找和B的根节点相同的结点，重复步骤，直到有任何一棵二叉树为空退出
3 C++核心代码
3.1 递归实现1
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//1.先找到和子树根节点相同的结点
bool flag=false;
if((pRoot1!=NULL)&&(pRoot2!=NULL))
{
if(pRoot1->val==pRoot2->val)
//开始判断，此时找到了和子树根节点相同的结点
flag=HasSubtreetty(pRoot1, pRoot2); if(!flag) flag=HasSubtree(pRoot1->left, pRoot2); if(!flag) flag=HasSubtree(pRoot1->right, pRoot2);
}
return flag;
} bool HasSubtreetty(TreeNode* pRoot1, TreeNode* pRoot2)
{
//该函数需要判断在找到和子树根节点相同的结点之后，判断其余结点是否相同
if(pRoot2==NULL)
return true;
if((pRoot1==NULL)&&(pRoot2!=NULL))
return false;
if(pRoot1->val!=pRoot2->val)
return false;
return HasSubtreetty(pRoot1->left, pRoot2->left)&&HasSubtreetty(pRoot1->right, pRoot2->right);
}
};
3.2 递归实现2
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool IsSubtree(TreeNode* p1, TreeNode* p2)
{
if(p2==NULL)return ;
if(p1==NULL)return ; if(p1->val != p2->val)return ; return IsSubtree(p1->left,p2->left) && IsSubtree(p1->right,p2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1==NULL || pRoot2==NULL)return ; return IsSubtree(pRoot1,pRoot2)||
HasSubtree(pRoot1->left,pRoot2) ||
HasSubtree(pRoot1->right,pRoot2);
}
};
4 完整代码
#include <iostream>
using namespace std;
//struct ListNode {
// int val;
// struct ListNode *next;
// ListNode(int x) : val(x), next(NULL) {}
//};
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//1.先找到和子树根节点相同的结点
bool flag = false;
if ((pRoot1 != NULL) && (pRoot2 != NULL))
{
if (pRoot1->val == pRoot2->val)
//开始判断，此时找到了和子树根节点相同的结点
flag = HasSubtreetty(pRoot1, pRoot2);
if (!flag)
flag = HasSubtree(pRoot1->left, pRoot2);
if (!flag)
flag = HasSubtree(pRoot1->right, pRoot2);
}
return flag;
}
bool HasSubtreetty(TreeNode* pRoot1, TreeNode* pRoot2)
{
//该函数需要判断在找到和子树根节点相同的结点之后，判断其余结点是否相同
if (pRoot2 == NULL)
return true;
if ((pRoot1 == NULL) && (pRoot2 != NULL))
return false;
if (pRoot1->val != pRoot2->val)
return false;
return HasSubtreetty(pRoot1->left, pRoot2->left) && HasSubtreetty(pRoot1->right, pRoot2->right);
}
};
int main()
{
Solution *s = new Solution();
TreeNode *t1 = new TreeNode();
TreeNode *t2 = new TreeNode();
TreeNode *t3 = new TreeNode();
TreeNode *t4 = new TreeNode();
TreeNode *t5 = new TreeNode();
TreeNode *t6 = new TreeNode();
TreeNode *t7 = new TreeNode();
TreeNode *t8 = new TreeNode();
TreeNode *t9 = new TreeNode();
t1->left = t2; t1->right = t3;
t2->left = t4; t2->right = t5; t3->left = t6; t3->right = t7;
t4->left = t8; t4->right = t9;
TreeNode *tt1 = new TreeNode(); //只有8 6相同时也是子树，返回值为1
//TreeNode *tt2 = new TreeNode(6);
//TreeNode *tt3 = new TreeNode(5);
TreeNode *tt2 = new TreeNode();
TreeNode *tt3 = new TreeNode();
tt1->left = tt2; tt1->right == tt3;
bool out_tree = s->HasSubtree(t1, tt1);
cout << out_tree << endl;
system("pause");
return ;
}
参考资料
https://blog.csdn.net/weixin_36125166/article/details/75939373
https://blog.csdn.net/danxibaoxxx/article/details/93402407
