另一棵树的子树

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

572. 另一棵树的子树 - 力扣（LeetCode） (leetcode-cn.com)

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

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

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：

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

->说明root和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;
    }
    //递归判断p和q的左子树和右子树是否相等
    //二者都相同，一整棵树才是相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
​
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    //subroot不可能为NULL,如果root为空，说明不是相同的树
    if(root == NULL)
    {
        return false;
    }
    //root和subroot两棵树完全相同
     if(isSameTree(root,subRoot))
     {
         return true;
     }
     //以左子树和右子树为根，递归下去找和subRoot相同的树
     // 用 || 一个为true 就说明找到了
     return isSubtree(root->left,subRoot) 
         || isSubtree(root->right,subRoot);
}

本质和查找很像查找返回的是结点 这里返回的是真假

先跟当前根结点的子树比较，相等了返回true，不相等则去左树比较，左数找到了就不用去右树找，

左树没找到就去右树找左边右边都没有找到就返回结果给上一层

最坏情况:

每个子树都要比较，且都要比较到最后一个结点

O(N^2)

注意事项

不要写成
    return isSameTree(root->left,subRoot) 
         || isSameTree(root->right,subRoot);

我们是希望：以某一个节点为根结点的树，判断和subroot是否相同

• 因为这里是检测是否为子树的 而不是检测是否相同的

• 检测什么 就递归什么

• 是否相同只是子树的一种情况 如果直接递归调用是否相同 那只能过部分用例

  • 两棵树如果相同 可以认为是子树
  • 但是是子树的话 两棵树不一定相同

\