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

面试题 时间:2019-09-22 手机网站

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

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一样的结构。