菜鸟笔记
提升您的技术认知

《剑指offer》树的子结构-ag真人游戏

阅读 : 647

题目描述:

  输入两棵二叉树a,b,判断b是不是a的子结构。(ps:我们约定空树不是任意一个树的子结构)

解题思路:

  要查找树a中是否存在和树b结构一样的子树,我们可以分为两步:第一步,在树a中找到和树b的根结点值一样的结点r;第二步,判断树a中以r为根结点的子树是不是包含和树b一样的结构。

  对于这两步,第一步实际上就是树的遍历,第二步是判断是否有相同的结构,这两步都可以通过递归来实现。

  举例:

代码实现(c )

/*
struct treenode {
    int val;
    struct treenode *left;
    struct treenode *right;
    treenode(int x) :
            val(x), left(null), right(null) {
    }
};*/
class solution {
public:
    bool hassubtree(treenode* proot1, treenode* proot2)
    {
        bool result = false;
        if(proot1 != null && proot2 != null){
            if(proot1->val == proot2->val){
            result = doestree1hastree2(proot1, proot2);
        }
            if(!result){
                result = hassubtree(proot1->left, proot2);
            }
            if(!result){
                result = hassubtree(proot1->right, proot2);
            }
        }
        return result;
    }
private:
    bool doestree1hastree2(treenode* proot1, treenode* proot2){
        if(proot2 == null){
            return true;
        }
        if(proot1 == null){
            return false;
        }
        if(proot1->val != proot2->val){
            return false;
        }
        return doestree1hastree2(proot1->left, proot2->left) && doestree1hastree2(proot1->right, proot2->right);
    }
};
网站地图