LeetCode——572—— 另一棵树的子树

简介: LeetCode——572—— 另一棵树的子树

1.题目



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


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

image.png

示例 1:


输入:root = [3,4,5,1,2], subRoot = [4,1,2]

输出:true

示例 2:

image.png


输入: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


2.解析



首先我们可以知道root为空时肯定不存在即返回false;


第二点我们可以套用LeetCode——100——相同的树的思路bool isSameTree判断是否相同;


我们可以考虑递归找root->val==subRoot->val时进行比较此时root和subRoot是否相同,


我们不能直接写


if(root->val==subRoot->val)
   return (isSameTree(root,subRoot));

但此时我们需要考虑以下这种情况


image.png


因此我们要改为限制条件 ,实现不断对比,查找是否存在 root 中是否包含和 subRoot 具有相同结构和节点值的子树;


if(root->val==subRoot->val)
{
    if(isSameTree(root,subRoot))
    {
          return true;
    }
}

root左右子树递归查看


3.代码实现


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(root->val==subRoot->val)
{
    if(isSameTree(root,subRoot))
    {
          return true;
    }
}
 return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}


将代码


if(root->val==subRoot->val)
{
    if(isSameTree(root,subRoot))
    {
          return true;
    }
}
 return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

可升华为


return isSameTree(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);

最终代码


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;
}
 return isSameTree(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

image.png

相关文章
|
2月前
|
算法 C语言 容器
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
39 7
|
2月前
|
C语言
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
30 1
|
2月前
|
算法 C语言 C++
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
21 1
|
2月前
LeetCode———100——相同的树
LeetCode———100——相同的树
|
2月前
力扣337.打家劫舍3(树形dp)
力扣337.打家劫舍3(树形dp)
|
1月前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
1月前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
1月前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
1月前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
1月前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
12 0