程序员面试题精选100题（50）-树的子结构[数据结构] (2)

                第一步在树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);