面试题26：树的子结构

题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：

struct BinaryTreeNode
{
    double                 m_dbValue;
    BinaryTreeNode*        m_pLeft;
    BinaryTreeNode*        m_pRight;
};

解题思路

1. 在树A中查找于根节点的值一样的节点，这实际上就是树的遍历。
2. 判断树A中以R为根节点的子树是不是和树B具有相同的结构。

错误示范

bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
    if (pRoot1 == nullptr || pRoot2 == nullptr) {
        return false;
    }

    bool left, right;
    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);
            //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)) {
            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 则该怎么处理。另外还有个细节，在判断两个小数是否相等时，只能判断它们之差的绝对值是不是在一个很小的范围内，而不能直接使用 == 符号。

相关链接

• 本题完整的源代码：zhedahht/CodingInterviewChinese2/26_SubstructureInTree
• 树的子结构_牛客网