剑指offer-树的子结构

客官°小女子只卖身不卖艺 2022-02-13 15:01 210阅读 0赞

#### 题目描述 ####

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

#### 算法实现 ####

本博客没有写实现思想，但是在算法实现中已经用注释的办法，将实现思想写在了代码中，由于本题算法不容易理解，利用注释的办法可以更好的让大家理解算法的实现过程。

/*
    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)
        {
            //判断是否两个其中一个为空，如果其中一个为空，返回false
            if(pRoot1 == NULL || pRoot2 == NULL) return false;
            //如果两个都不为空，先进行是否为子结构的判断，
            //然后进行pRoot1左子树是否有子结构，在进行右子树是否有子结构
            //只要一个有子结构就可以返回True，所以这用或连接
            return isHasSubtree(pRoot1, pRoot2) ||
                HasSubtree(pRoot1->left, pRoot2) ||
                HasSubtree(pRoot1->right, pRoot2);
        }
        //判断是否是子结构的递归函数
        bool isHasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
        {
            //如果pRoot2子树先为空了，说明是子结构
            if(pRoot2 == NULL) return true;
            //如果子树没有为空，pRoot1为空了，说明不是子结构
            if(pRoot1 == NULL) return false;
            //如果相等，就继续比较左子树和右子树是否都为子结构
            //因为必须要求左右子树都为子结构才能说整颗pRoot2为pRoot1的子结构，所以用&&
            if(pRoot1->val == pRoot2->val) 
                return isHasSubtree(pRoot1->left, pRoot2->left) && 
                isHasSubtree(pRoot1->right, pRoot2->right);
            //如果不相等，就返回false
            else
                return false;
        }
    };

#### 运行截图 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]

#### 总结 ####

本题主要是利用了递归的思想遍历整棵树，先遍历看此节点是否与子树根节点相同，如果相同跳到另一个函数递归看其他的节点是否也相同。如果此节点不与子树根节点相同，就看左子树的节点和右子树的节点是否与子树根节点相同，依次这样递归。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]: /images/20220213/c0af610bb2fb47d8890459febcb2d0e9.png