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

题目描述：

  输入两棵二叉树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);
    }
};