题解 | #树的子结构#
树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
一.递归
在A树中先序访问并比较结点，遇到与B树头结点值相等时，以A树当前结点为头结点再同时对A子树与B树先序访问并比较。
//先序遍历（递归）判断
#include <stdbool.h>
bool match(struct TreeNode* p1,struct TreeNode* p2){//用来判断后者是否为前者的子树
if(!p2){//匹配树访问完毕，匹配成功
return true;
}
if(!p1){//被匹配树已访问完毕，匹配树还有结点未访问，匹配失败
return false;
}
if(p1->val!=p2->val){//当前结点不匹配，匹配失败
return false;
}
//匹配当前结点左右子树，顺序为根->左->右
return match(p1->left,p2->left) && match(p1->right,p2->right);
}
bool HasSubtree(struct TreeNode* pRoot1, struct TreeNode* pRoot2 ) {
// write code here
if(!pRoot1 || !pRoot2){
return false;
}
bool flag=match(pRoot1,pRoot2);//判断当前的子树部分是否与B树匹配
bool flag_left=HasSubtree(pRoot1->left,pRoot2);//判断左分支中是否有与B树匹配的子树
bool flag_right=HasSubtree(pRoot1->right,pRoot2);//判断右分支中是否有与B树匹配的子树
return flag || flag_left || flag_right;
}
二.利用辅助队列（纯C不推荐）
和先序遍历一样的思路，由于层次遍历不是基于递归，而是利用辅助队列储存结点值再访问。对比时需要用到3个辅助队列，有一定的空间开销。虽然逻辑好理解，但边界条件多，操作还复杂，特别是进出队操作加上了第二层的层次遍历，写完代码太浪费时间。
//层次遍历（辅助队列）判断
#include <stdbool.h>
bool HasSubtree(struct TreeNode* pRoot1, struct TreeNode* pRoot2 ) {
// write code here
if(!pRoot1 || !pRoot2){
return false;
}
struct TreeNode *p1=pRoot1,*p2=pRoot2;
//最后一个示例结点总数有29326个，超出了题目的数据范围
int **p1_queue=(int**)malloc(15000*sizeof(int*));//存储A树结点地址
int **p2_queue=(int**)malloc(15000*sizeof(int*));//存储B树结点地址
int **temp=(int**)malloc(15000*sizeof(int*));//层次遍历A的子树的临时队列，用于储存子树结点地址
int p1_top=-1,p1_rear=-1,p2_top=-1,p2_rear=-1;//定义队首，队尾指针
p1_queue[++p1_rear]=pRoot1;
p2_queue[++p2_rear]=pRoot2;
while(p1_top!=p1_rear && p2_top!=p2_rear){//层次遍历，用数组存储访问过的值
p1=p1_queue[++p1_top];
p2=p2_queue[++p2_top];
if(p1->val==p2->val){
int temp_top=-1,temp_rear=-1;
p2_top=-1;p2_rear=0;
temp[++temp_rear]=p1;
while(temp_top!=temp_rear && p2_top!=p2_rear){
p1=temp[++temp_top];
p2=p2_queue[++p2_top];
if(p1->val==p2->val){
if(p1->left && p2->left){
temp[++temp_rear]=p1->left;
p2_queue[++p2_rear]=p2->left;
}
else if(!p1->left && p2->left){
p2_top=-1;p2_rear=0;
break;
}
if(p1->right && p2->right){
temp[++temp_rear]=p1->right;
p2_queue[++p2_rear]=p2->right;
}
else if(!p1->right && p2->right){
p2_top=-1;p2_rear=0;
break;
}
}
else{
p2_top=-1;p2_rear=0;
break;
}
}
if(p2_top==p2_rear){
return true;
}
}
p2_top=-1;p2_rear=0;//重置对比进度
p1=p1_queue[p1_top];
if(p1->left){
p1_queue[++p1_rear]=p1->left;
}
if(p1->right){
p1_queue[++p1_rear]=p1->right;
}
}
//free(p1_queue);free(p2_queue);free(temp);//NO FREE
if(p2_top!=p2_rear){//若pRoot2树还有剩余则匹配失败
return false;
}
return true;
}
查看16道真题和解析
汤臣倍健公司氛围 420人发布
