leetcode 572. 另一颗树的子树

2023-12-14 21:34:15

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

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


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

文章来源:https://blog.csdn.net/2301_79789645/article/details/135003744
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。