Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >​LeetCode刷题实战572:另一棵树的子树

​LeetCode刷题实战572:另一棵树的子树

作者头像
程序员小猿
发布于 2022-04-12 11:21:04
发布于 2022-04-12 11:21:04
23300
代码可运行
举报
文章被收录于专栏:程序IT圈程序IT圈
运行总次数:0
代码可运行

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 另一棵树的子树,我们先来看题面:

https://leetcode-cn.com/problems/subtree-of-another-tree/

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

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

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

示例

解题

这道题就是在 root 的每个子节点上,判断由该子节点构成的子树是否和 subRoot 这颗树相等。判断两颗树相等需要同时满足三个条件:当前两颗树的根节点值相等;两颗树的左子树相等;两棵树的右子树相等。而判断 一棵树 是否为 另一颗树 的子树只需满足以下条件中的一个:当前两棵树相等;或 一棵树 是 另一颗树 的左子树;或 一棵树 是 另一棵树 的右子树。此题采用递归法求解。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root==NULL||subRoot==NULL)
            return false;
        if(root->val!=subRoot->val){
            return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
        }else{
            // return judge(root,subRoot);
            return judge(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); // 这是为了应对出现有重复元素出现的情况,比如root: 1 1, subroot:1
        }
        return false;
    }
    bool judge(TreeNode* root1, TreeNode* root2){
        // 这是用来判断子树的
        if(root1==NULL&&root2==NULL) // 两个都为空,说明比对完了,返回true
            return true;
        if(root1==NULL||root2==NULL) // 其中一个为空,说明一个比完,一个还有,返回false
            return false;
        // 如果是判断子结构的就用下面这种方式
        // if(root2==NULL)
        // return true;
        // if(root1==NULL) // 此时肯定root2不为null,root1为null,所以false;
        // return false;
        if(root1->val!=root2->val)
            return false;
        else 
            return judge(root1->left,root2->left)&&judge(root1->right, root2->right);
    }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-560题汇总,希望对你有点帮助!

LeetCode刷题实战561:数组拆分 I

LeetCode刷题实战562:矩阵中最长的连续1线段

LeetCode刷题实战563:二叉树的坡度

LeetCode刷题实战564:寻找最近的回文数

LeetCode刷题实战565:数组嵌套

LeetCode刷题实战566:重塑矩阵

LeetCode刷题实战567:字符串的排列

LeetCode刷题实战568:最大休假天数

LeetCode刷题实战569:员工薪水中位数

LeetCode刷题实战570:至少有5名直接下属的经理

LeetCode刷题实战571:给定数字的频率查询中位数

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-04-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小猿 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
每日算法题:Day 9
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
算法工程师之路
2019/08/13
3740
二叉树模板套题——相同的树的应用
力扣100. 相同的树 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入:p = [1,2,3], q = [1,2,3] 输出:true 示例 2: 输入:p = [1,2], q = [1,null,2] 输出:false 示例 3: 输入:p = [1,2,1], q = [1,1,2] 输出:false /** * Definition for a binary tree nod
lovevivi
2022/12/05
2220
二叉树模板套题——相同的树的应用
【Leetcode -617.合并二叉树 -1022.从根到叶的二进制数之和】
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。 返回合并后的二叉树。 注意 : 合并过程必须从两个树的根节点开始。
YoungMLet
2024/03/01
1430
【Leetcode -617.合并二叉树 -1022.从根到叶的二进制数之和】
二叉树OJ题——9.另一棵树的子树
绝活蛋炒饭
2024/12/16
710
二叉树OJ题——9.另一棵树的子树
二叉树基础oj练习(对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历)
是Nero哦
2024/01/18
1670
二叉树基础oj练习(对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历)
【关关的刷题日记57】Leetcode 101. Symmetric Tree
关关的刷题日记57 – Leetcode 101. Symmetric Tree 题目 题目的意思是判断一棵树是否是镜像的,此处镜像指的是中心对称的树。 思路 思路:一棵树如果是镜像的,那么它的左右节
WZEARW
2018/04/11
6780
【关关的刷题日记57】Leetcode 101. Symmetric Tree
【Leetcode】相同的树、对称二叉树、另一颗树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
P_M_P
2024/01/18
1660
【Leetcode】相同的树、对称二叉树、另一颗树的子树
【数据结构与算法 经典例题】判断一棵树是否是另一棵树的子树
倔强的石头_
2024/12/06
1580
【数据结构与算法 经典例题】判断一棵树是否是另一棵树的子树
【Leetcode -965.单值二叉树 -572.另一颗树的子树】
题目:如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时,才返回 true;否则返回 false。
YoungMLet
2024/03/01
1120
【Leetcode -965.单值二叉树 -572.另一颗树的子树】
力扣572:另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
南桥
2024/01/26
1610
力扣572:另一棵树的子树
LeetCode——572—— 另一棵树的子树
. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
小李很执着
2024/06/15
1070
LeetCode——572—— 另一棵树的子树
刚学完二叉树,来试试这些oj题练练手吧!
二叉树 主要就是玩递归,相信大家学完 二叉树 以后,对递归有了更加深层的理解,可以试着做几道oj题,练一下手.
初阶牛
2023/10/14
1660
刚学完二叉树,来试试这些oj题练练手吧!
C语言每日一题(55)另一颗树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
对编程一片赤诚的小吴
2024/02/13
1020
C语言每日一题(55)另一颗树的子树
【Leetcode】二叉树基础题思路
单值二叉树是所有节点的值都相同的二叉树。实现这个检查的思路是通过递归方式遍历整棵树,并验证每个节点是否满足单值二叉树的条件
用户11029103
2024/05/04
1260
【Leetcode】二叉树基础题思路
【数据结构】翻转、平衡、对称二叉树,最大深度、判断两棵树是否相等、另一棵树的子树
若要让时间复杂度为O(n),则需要在判断的过程中,只要发现左右俩树高度相差大于 1,就直接 return -1,不再进行后续判断了
椰椰椰耶
2024/10/15
1350
【数据结构】翻转、平衡、对称二叉树,最大深度、判断两棵树是否相等、另一棵树的子树
【数据结构与算法 经典例题】判断二叉树是否对称
倔强的石头_
2024/12/06
1460
【数据结构与算法 经典例题】判断二叉树是否对称
leetcode:对称二叉树
写一个子函数对比左右子树:用递归的思路,左子树的左子树和右子树的右子树对比,左子树的右子树和右子树的左子树对比,我们只需要考虑几种情况:
用户10925563
2024/06/04
960
leetcode:对称二叉树
leetcode 872. 叶子相似的树
叶子相似的树题解汇总 DFS 同步遍历 ---- DFS 写法1: class Solution { public: bool leafSimilar(TreeNode* root1, TreeNode* root2) { vector<int> v1; vector<int> v2; dfs(root1, v1); dfs(root2, v2); return v1 == v2; } void dfs(TreeNode* root, vector<int>& v)
大忽悠爱学习
2021/11/15
2280
【初阶数据结构篇】二叉树OJ题
根节点与左右孩子的数值进行比较,如果相等依次递归左右子树,如果为空,或者两者对应的值相等,则返回true。若不相等则直接返回false。
熬夜学编程的小王
2024/11/20
750
【初阶数据结构篇】二叉树OJ题
题目练习之二叉树那些事儿
既然这里涉及到保存数据的比较,那么肯定需要遍历我们的二叉树了,具体怎么比较呢?我们给出思路~
用户11352420
2024/11/07
760
题目练习之二叉树那些事儿
推荐阅读
相关推荐
每日算法题:Day 9
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档