注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

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

2010-12-04 17:08:39|  分类: |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:二叉树的结点定义如下:

struct TreeNode

{

        int m_nValue;

        TreeNode* m_pLeft;

        TreeNode* m_pRight;

};

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

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

                 1                                                   8
               /    \                                               /    \
              8    7                                             9    2
            /    \
           9    2
                /  \
               4  7

分析:这是2010年微软校园招聘时的一道题目。二叉树一直是微软面试题中经常出现的数据结构。对微软有兴趣的读者一定要重点关注二叉树。

                回到这个题目的本身。要查找树A中是否存在和树B结构一样的子树,我们可以分为两步:第一步在树A中找到和B的根结点的值一样的结点N,第二步再判断树A中以N为根结点的子树是不是包括和树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;

}

在上述代码中,我们递归调用hasSubtreeCore遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同,则调用DoesTree1HaveAllNodeOfTree2,做第二步判断。

在面试的时候,我们一定要注意边界条件的检查,即检查空指针。当树A或树B为空的时候,定义相应的输出。如果没有检查并做相应的处理,程序非常容易崩溃,这是面试时非常忌讳的事情。由于没有必要在每一次递归中做边界检查(每一次递归都做检查,增加了不必要的时间开销),上述代码只在HasSubtree中作了边界检查后,在HasSubtreeCore中作递归遍历。

接下来考虑第二步,判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样,我们也可以用递归的思路来考虑:如果结点N的值和树B的根结点不相同,则以N为根结点的子树和树B肯定不具有相同的结点;如果他们的值相同,则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。参考代码如下:

bool DoesTree1HaveAllNodesOfTree2(TreeNode* pTreeHead1, TreeNode* pTreeHead2)

{

        if(pTreeHead2 == NULL)

                return true;

 

        if(pTreeHead1 == NULL)

                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);

}

 

  本文已经收录到《剑指Offer——名企面试官精讲典型编程题》一书中,有改动,书中的分析讲解更加详细。欢迎关注。

    博主何海涛对本博客文章享有版权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。

  评论这张
 
阅读(24876)| 评论(49)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017