【剑指offer】二叉树的子结构，C++实现（递归）

原创博文，转载请注明出处！

《牛客链接》

1.题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：约定空树不是任意一个树的子结构）

图1.二叉树A和二叉树B

2.思路（递归）

查找二叉树B是否是二叉树A的子结构，可以分为两步：

第一步，递归遍历树A，在树A中找到和树B的根节点的值一样的节点R。递归出口是遍历完二叉树A或在树A中找到和树B结构一样的子树。

树A为空的时候，输出false
树B为空的时候，输出false

第二步，递归遍历树A的子树，判断树A中以R为根节点的子树是不是包含和树B一样的结构。递归出口是到达树A或者树B的叶节点。

如果树B的指针为空，则返回true
如果树B的指针不为空，而树A的指针为空，则返回false

图2.树A的根节点和树B的根节点的值相同，但树A的根节点下面的结构和树B的结构不一致

图3.在树A中找到第二个值为8的节点，该节点存在和B的结构一样的子树

3.代码

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

};*/

class Solution {

public:

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)

    {

        // 递归出口

        if(!pRoot1||!pRoot2)

            return false;

        return ( dfs(pRoot1,pRoot2)) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);

    }

private:

    bool dfs(TreeNode * r1, TreeNode * r2)

    {

        // 递归出口

        if(!r2)

            return true;

        // 递归出口

        if(!r1)

            return false;

        // 递归出口

        if(r1->val != r2->val)

            return false;

        else

            return dfs(r1->left, r2->left) && dfs(r1->right, r2->right);

    }

};

4.测试用例

# 边界测试

树A的头结点是空指针
树B的头结点是空指针
树A和树B的头结点是空指针
树A和树B只有左子节点或右子节点

# 功能测试

普通二叉树，树B是树A的子结构
普通二叉树，树B不是树A的子结构

巴特西

【剑指offer】二叉树的子结构，C++实现（递归）

1.题目

2.思路（递归）

3.代码

4.测试用例

最新文章

热门文章