软件工程师面试题精选100题(50)-树为另一树的子结构

程序员面试题精选100题(50)-树为另一树的子结构
题目：二叉树的结点定义如下：

struct TreeNode
{
        int m_nValue;
        TreeNode* m_pLeft;
        TreeNode* m_pRight;
};

输入两棵二叉树A和B，判断树B是不是A的子结构。

例如，下图中的两棵树A和B，由于A中有一部分子树的结构和B是一样的，因此B就是A的子结构。

bool HasSubtree(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{//主要进行特殊条件的判断
        if((pTreeHead1 == NULL && pTreeHead2 != NULL) ||
               (pTreeHead1 != NULL && pTreeHead2 == NULL))
                return false;
        if(pTreeHead1 == NULL && pTreeHead2 == NULL)
                return true;
        return HasSubtreeCore(pTreeHead1, pTreeHead2);
}
bool HasSubtreeCore(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
        bool result = false;
        if(pTreeHead1->m_nValue == pTreeHead2->m_nValue)
        {//根节点相同再进行进一步判断，如果根节点都不同就不用进一步判断了
              result = DoesTree1HaveAllNodesOfTree2(pTreeHead1, pTreeHead2);
        }
        if(!result && pTreeHead1->m_pLeft != NULL)
                result = HasSubtreeCore(pTreeHead1->m_pLeft, pTreeHead2);
        if(!result && pTreeHead1->m_pRight != NULL)
                result = HasSubtreeCore(pTreeHead1->m_pRight, pTreeHead2);
        return result;
}

bool DoesTree1HaveAllNodesOfTree2(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
        if(pTreeHead2 == NULL) //如果pTree2都弄完了还没return说明符合要求
                return true;
        if(pTreeHead1 == NULL)//如果 pTree2没弄完，pTree1就弄玩了，说明pTree1还少了东西，肯定返回false
                return false;
        if(pTreeHead1->m_nValue != pTreeHead2->m_nValue)
                return false;
        return DoesTree1HaveAllNodesOfTree2(pTreeHead1->m_pLeft, pTreeHead2->m_pLeft) &&
                DoesTree1HaveAllNodesOfTree2(pTreeHead1->m_pRight, pTreeHead2->m_pRight);

}