【力扣刷题实战】另一棵树的子树

大家好，我是小卡皮巴拉

文章目录

力扣题目：另一棵树的子树

题目描述

示例 1：

示例 2：

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C语言）

兄弟们共勉！！！

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：另一棵树的子树

原题链接：另一棵树的子树

题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

解题思路

问题理解

题目要求检查二叉树 root 中是否包含与 subRoot 具有完全相同结构和节点值的子树。

算法选择

使用递归方法，通过遍历 root 并在每个节点处检查是否与 subRoot 相同。

具体思路

定义一个辅助函数 isSameTree，用于检查两棵树是否完全相同。

在主函数 isSubtree 中，对 root 进行遍历，并对每个节点调用 isSameTree 进行检查。

如果在某个节点处找到了与 subRoot 相同的子树，则返回 true。

如果遍历完所有节点仍未找到，则返回 false。

解题要点

定义树节点结构：typedef struct TreeNode TreeNode; 已经在代码开头定义。

编写 isSameTree 函数：比较两棵树 p 和 q 是否完全相同。

编写 isSubtree 函数：递归遍历 root 并调用 isSameTree 进行检查。

完整代码（C语言）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL)
    {
        return true;
    }
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //都不为空
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{
    if(root == NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    //root和subRoot不是相同的树——subRoot不是root的子树
    //继续递归
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}