leetcode 572. 另一颗树的子树
2023-12-14 21:34:15
这道题重在思路,默认大家会判断两个树是否完全相同
我会把一些基础的简单的(包括? 判断两个树是否完全相同? 和之前的 求结点个数 )单独出博客,或者放在介绍堆和树的知识点里面
572. 另一颗树的子树
题目
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
题目链接
文字 和 画图 分析
- 这里用到的思路其实是 判断两棵树是否完全相同 的变形
知道这一点,整个思路就出来了,只要遍历 root 这棵树的结点就行
? ? ?2. 递归结束条件 和 进行条件
传过去的结点一定不能是空树,
所以 root == NULL(这是结束条件)
进行条件就是 和它相反
[只判断一个根结点是无法确定是否是另一棵的子树]
代码
bool Issample(struct TreeNode* root,struct TreeNode* subRoot)
{
if(root == NULL && subRoot == NULL)
{
return true;
}
if(root == NULL || subRoot == NULL)
{
return false;
}
if(root->val != subRoot->val)
{
return false;
}
return Issample(root->left,subRoot->left)
&& Issample(root->right,subRoot->right) ;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
if(root == NULL)
{
return false;
}
if(Issample(root, subRoot))
{
return true;
}
return isSubtree(root->left, subRoot)
|| isSubtree(root->right, subRoot);
}
文章来源:https://blog.csdn.net/2301_79789645/article/details/135003744
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!