题目描述
输入两棵二叉树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则该怎么处理。另外还有个细节,在判断两个小数是否相等时,只能判断它们之差的绝对值是不是在一个很小的范围内,而不能直接使用==符号。