leetcode 572. 另一颗树的子树

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

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

572. 另一颗树的子树

题目

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

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

题目链接

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

文字 和 画图 分析

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

知道这一点，整个思路就出来了，只要遍历 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);
}