leetcode 572. 另一颗树的子树

这篇具有很好参考价值的文章主要介绍了leetcode 572. 另一颗树的子树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这道题重在思路，默认大家会判断两个树是否完全相同

我会把一些基础的简单的（包括判断两个树是否完全相同和之前的求结点个数）单独出博客，或者放在介绍堆和树的知识点里面

572. 另一颗树的子树

题目

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

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

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

文字和画图分析

这里用到的思路其实是判断两棵树是否完全相同的变形

知道这一点，整个思路就出来了，只要遍历 root 这棵树的结点就行

2. 递归结束条件和进行条件

传过去的结点一定不能是空树，

所以 root == NULL(这是结束条件)

进行条件就是和它相反

[只判断一个根结点是无法确定是否是另一棵的子树]文章来源地址https://www.toymoban.com/news/detail-765731.html

代码

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);
}

到了这里，关于leetcode 572. 另一颗树的子树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！