题目地址：剑指 Offer 26. 树的子结构 - 力扣（LeetCode）
目录
对于二叉树类的题目，一般会使用递归或层序遍历的思路来解决。
对于该题，我们思考后会发现递归就能解决问题。
那么思路就出来了。
因为题目中说明B是A的子结构（或不是），那么B应该小于等于A的大小。
所以选B的树顶作为参照物，从A的树顶开始依次匹配。
当A中节点与B的树顶匹配时，再匹配B中剩下节点，全部一致True;不一致False。
如果False，再开始将B树顶与A剩下节点匹配，直到True或A全部匹配结束False。
因为过程非常模块化，我们完全可以通过多个函数来组合实现，这样代码可读性高。
除了主函数外，我们可以写一个Search函数来寻找A与B树顶匹配节点。
再写一个Judge函数来确定当B树顶与A匹配时剩下节点是否匹配。
该函数采用递归的方式进行，总体有两个情况。
①此时节点与B树顶匹配，此时交给Judge函数判断B是否是A子树。
若是，返回True。不是，就继续递归A节点左右子树。
②此时节点与B树顶不匹配，直接递归A节点左右子树。
返回条件：
当A递归到空时，返回False，因为空了就说明这条路上没有能给B匹配的。
需要注意的是，递归时，左右子树的关系是或，当左或右有一个能有B树匹配即可。
该函数的中心思想是查看此时AB节点是否匹配，若匹配就继续判断A左B左以及A右B右。
若不匹配就返回False。
注意：
当B节点到空时，此时说明B中某一分支已经匹配完毕且与A完全一致，直接返回True。
当A节点空时（B不空），此时说明A与B并不匹配，返回False。
PS：看完思路不妨自己先实现一下。
class Solution {
public:
bool Judge(TreeNode* a, TreeNode* b)
{
if(b == nullptr) return true;
if(a == nullptr) return false;
if(a->val != b->val) return false;
return Judge(a->left, b->left) && Judge(a->right, b->right);//注意是&&的关系
}
bool Search(TreeNode* a, TreeNode* b)
{
if(a == nullptr) return false;
if(a->val == b->val && Judge(a, b)) return true;
return Search(a->left, b) || Search(a->right, b);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A == nullptr || B == nullptr) return false;//判空
return Search(A, B);
}
};本题也可以使用非递归的方式来实现。
我们只需要将Search函数和Judge函数改造成层序遍历A树即可。
bool Search(TreeNode* a, TreeNode* b)
{
queue<TreeNode*> qu;
qu.push(a);
while(!qu.empty())
{
TreeNode* tmp = qu.front();
qu.pop();
if(tmp->val == b->val && Judge(tmp, b)) return true;
if(tmp->left) qu.push(tmp->left);
if(tmp->right) qu.push(tmp->right);
}
return false;
}bool Judge(TreeNode* a, TreeNode* b)
{
queue<TreeNode*> qua, qub;
qua.push(a);
qub.push(b);
while(!qub.empty())
{
TreeNode* tmpa = qua.front(), *tmpb = qub.front();
if(tmpa->val != tmpb->val) return false;
if(tmpb->left)
{
if(tmpa->left == nullptr) return false;
qua.push(tmpa->left);
qub.push(tmpb->left);
}
if(tmpb->right)
{
if(tmpa->right == nullptr) return false;
qua.push(tmpa->right);
qub.push(tmpb->right);
}
qub.pop();qua.pop();
}
return true;
}
先把数据结构搞清楚，程序的其余部分自现。—— David Jones
如有错误，敬请斧正