【leetcode】572.另一棵树的子树（附加图解）

文章目录

题目描述leetcode补充代码如下：代码详细讲解图解

题目描述

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

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
【leetcode】572.另一棵树的子树（附加图解）
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
提示：
• root 树上的节点数量范围是 [1, 2000]
• subRoot 树上的节点数量范围是 [1, 1000]
• -104 <= root.val <= 104
• -104 <= subRoot.val <= 104

leetcode补充代码如下：


bool isSametree(struct TreeNode* p,struct TreeNode* q)//以该节点为根的子树” 是否与 subRoot 完全相同（包括所有左右子树）
{
    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;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}//找的是root起点的可能性

代码详细讲解


bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root==NULL)
    return false;
    if(isSametree(root,subRoot))
    return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}//找的是root起点的可能性

这段代码是以root为根结点的树和subRoot的树传到isSametree函数逐一数值进行比较，如果返回true，则找到了相同的子树，如果是false，则将root的左子树再次传入函数进行比较，如果左子树找不到才开始找右子树，直到找到为止，因此这里是使用“||”的符号


bool isSametree(struct TreeNode* p,struct TreeNode* q)//以该节点为根的子树” 是否与 subRoot 完全相同（包括所有左右子树）
{
    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);
}

这段是比较树是否完全相同的代码，要求全部要一样（左子树和右子树），因此这里是使用“&&”的符号，一旦发现数值不一样，马上返回false