题目描述
输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：
struct BinaryTreeNode
{
double m_dbValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
解题思路
- 在树A中查找于根节点的值一样的节点，这实际上就是树的遍历。
- 判断树A中以R为根节点的子树是不是和树B具有相同的结构。
错误示范
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == nullptr || pRoot2 == nullptr) {
return false;
}
bool left, right;
// (1)
if (pRoot1->m_dbValue == pRoot2->m_dbValue) {
if (pRoot1->m_pLeft == nullptr && pRoot2->m_pLeft == nullptr) {
left = true;
} else {
left = HasSubtree(pRoot1->m_pLeft, pRoot2->m_pLeft); // (2)
//if (!left) {
// left = HasSubtree(pRoot1->m_pLeft, pRoot2);
// if (left) {
// return true;
// }
//}
}
if (pRoot1->m_pRight == nullptr && pRoot2->m_pRight == nullptr) {
right = true;
} else {
right = HasSubtree(pRoot1->m_pRight, pRoot2->m_pRight);
//if (!right) {
// right = HasSubtree(pRoot1->m_pRight, pRoot2);
// if (right) {
// return true;
// }
//}
}
return left && right;
} else {
if(pRoot1->m_pLeft && HasSubtree(pRoot1->m_pLeft, pRoot2)) { // (3)
return true;
} else if (pRoot1->m_pRight) {
return HasSubtree(pRoot1->m_pRight, pRoot2);
} else {
return false;
}
}
}
这段代码的问题在于，没有对遍历和判断进行区分，会导致在判断的时候传递了错误的信息。
以如下的二叉树A和B为例，这里的树B是树A的子结构。当我们在第 7 行这个选择语句判断树A和树B的根相同后，从第11行开始对他们的子树进行判断，此时又回到第7行的选择。由于 pRoot1->m_dbValue == 8，而 pRoot2->m_dbValue == 9，从而进入第32行的 else 分支这里，此次比较本应该到这里就结束，返回 false 了。但由于这个分支的设想本是在遍历过程中根节点不一致，继续遍历。但由于没有对遍历和判断进行区分，这里会将树B的左子树作为根，传递下去。
8 8
/ \ / \
8 7 9 2
/ \
9 2
/ \
4 7
此处可以对代码进行修改，增加一个布尔变量来指示本次递归，到底是在遍历，还是在比较。但由于代码设计过程中引入了大量的分支结构，逻辑十分不清晰（没错，我搞了半天才搞清楚到底是错在哪），再引入一个变量将会使代码更为复杂，所以解决这个BUG的方法，只能是将其重新写一遍。
在参考了书中的解释，（自以为）理解了之后，我写出了如下的代码：
错误示范二
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == nullptr || pRoot2 == nullptr) {
return false;
}
if (pRoot1->m_dbValue != pRoot2->m_dbValue) {
if (HasSubtree(pRoot1->m_pLeft, pRoot2)) {
return true;
} else {
return HasSubtree(pRoot1->m_pRight, pRoot2);
}
} else {
return HasSubtreeCore(pRoot1, pRoot2);
}
}
bool HasSubtreeCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot2 == nullptr) {
return true;
}
if (pRoot1 == nullptr || pRoot1->m_dbValue != pRoot2->m_dbValue) {
return false;
}
return (HasSubtreeCore(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
HasSubtreeCore(pRoot1->m_pRight, pRoot2->m_pRight));
}
这段代码的问题在于，在第13行这里，当在树A的根节点找到与树B根节点一样的值时，不能直接返回判断的结果。因为如果这里判断的结果为否，还需要继续遍历这棵树，查找是否有其他值一样的节点，而不是直接将整个问题的结论否定掉。
正确示范
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
bool result = false;
if (pRoot1 != nullptr && pRoot2 != nullptr) {
if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)) {
result = HasSubtreeCore(pRoot1, pRoot2);
}
if (!result) {
result = HasSubtree(pRoot1->m_pLeft, pRoot2);
}
if (!result) {
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}
}
return result;
}
bool HasSubtreeCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot2 == nullptr) {
return true;
}
if (pRoot1 == nullptr || !Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)) {
return false;
}
return (HasSubtreeCore(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
HasSubtreeCore(pRoot1->m_pRight, pRoot2->m_pRight));
}
bool Equal(double num1, double num2) {
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
return true;
} else {
return false;
}
}
反思
书中本题的讲解中也提到，在每次使用指针的时候，我们都要问问自己这个指针有没有可能是 nullptr，如果是 nullptr 则该怎么处理。另外还有个细节，在判断两个小数是否相等时，只能判断它们之差的绝对值是不是在一个很小的范围内，而不能直接使用 == 符号。
网友评论