软件工程师面试题精选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);}