剑指offer之树的子结构
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
思路
该题目最重要的是理解子结构的含义,下面给出一个例子:
图中 2 4 5 6这个树是同构的,这种情况特别容易被忽略掉,代码中已经着重标出来了。
代码分为两个部分进行,HasSubtree
函数是进行层次序遍历的函数,用于索引A树中的每个节点。对于索引到的每个节点,调用is_equal
这个函数进行同构判别,用到了左右分别递归判定的策略。在这里再次强调同构的特殊情况!
AC代码
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(pRoot2 == nullptr || pRoot1 == nullptr) {
return false;
}
TreeNode* p = pRoot1;
queue<TreeNode*>que;
que.push(p);
while(!que.empty()) { // 层次遍历
auto p = que.front();
que.pop();
if(is_equal(p, pRoot2)) {
return true;
}
if(p->left != nullptr) {
que.push(p->left);
}
if(p->right != nullptr) {
que.push(p->right);
}
}
return false;
}
// 判断两棵树是否相等
bool is_equal(TreeNode* pRoot1, TreeNode* pRoot2) {
if(pRoot1 == nullptr && pRoot2 == nullptr) { // 都是空的
return true;
} else if(pRoot1 == nullptr || pRoot2 == nullptr) { // 只有一个是空的
return false;
} else if(pRoot1->val != pRoot2->val) { // 都不空,值不相等
return false;
} else if(pRoot1->val == pRoot2->val && // 这里是一个坑....注意判别方式!!!!!!!
pRoot2->left == nullptr &&
pRoot2->right == nullptr) {
return true;
} else { // 最好是写成尾递归,编译优化
return is_equal(pRoot1->left, pRoot2->left) &&
is_equal(pRoot1->right, pRoot2->right);
}
}
};