( “树” 之 DFS) 572. 另一棵树的子树 ——【Leetcode每日一题】

news/2024/4/21 0:55:30/

572. 另一棵树的子树

给你两棵二叉树 rootsubRoot 。检验 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-10^4 <= root.val <= 10^4104<=root.val<=104
  • −104<=subRoot.val<=104-10^4 <= subRoot.val <= 10^4104<=subRoot.val<=104

思路:DFS

首先任意看一个节点的root.val,该节点可能等于subRoot.val,也可能不相等,共有两种可能,对应的也就有两种不同的操作:

  • root.val == subRoot.val时,则判断剩余的后代节点是否都相等,如果有其中一个不相等,则subRoot不是root的子树,返回false,如果走到叶子节点都相等的话返回true;
  • root.val != subRoot.val时, 则接着到root的左右节点比较,只要有其中一个满足子树,就返回true;
  • 递归上述两种情况则可判断是否存在子树。

代码:(Java、C++)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null || subRoot == null) {return false; }return dfs(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}public boolean dfs(TreeNode root, TreeNode subRoot) {if(root == null && subRoot == null) return true;if(root == null || subRoot == null || root.val != subRoot.val){return false;} return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);}
}

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root == NULL || subRoot == NULL) {return false; }return dfs(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}bool dfs(TreeNode* root, TreeNode* subRoot) {if(root == NULL && subRoot == NULL) return true;if(root == NULL || subRoot == NULL || root->val != subRoot->val){return false;} return dfs(root->left, subRoot->left) && dfs(root->right, subRoot->right);}
};

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度O(n∗m)O(n*m)O(nm)mroot的节点数,nsubRoot的节点数,对于每一个root上的点,都需要做一次深度优先搜索来和subRoot匹配,匹配一次的时间代价是 O(m)O(m)O(m)
  • 空间复杂度O(n)O(n)O(n),考虑到递归需要在栈上开辟空间,最大深度为n

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/42026.html

相关文章

防火墙NAT实验,双机热备实验

目录 NAT防火墙基础实验 源地址转换 服务器映射 域内双向NAT 域间双向NAT 双机热备基础实验 主备备份 负载分担 NAT防火墙基础实验 实验拓扑&#xff1a; 1.进入防火墙图形化页面进行配置 接口列表的配置 源地址转换 企业内部网络访问外部网络&#xff0c;进行源地…

《八次危机》速读笔记

文章目录书籍信息概览发展陷阱和中国经验1958—1976&#xff1a;工业化初期的3次危机及其外资外债背景1978—1997&#xff1a;改革以来3次内源性经济危机及其化解1997和2008年中国2次“输入型”危机的发生、应对及影响关于全球危机与中国对策研究书籍信息 书名&#xff1a;《八…

20230409英语学习

Dog Philosophy 101&#xff1a;What Dogs Teach Us About Life 狗狗教给我们的人生哲学 I recently was pleased to receive an honorary Doctor of Science Degree from the University of Guelph.As part of the ceremony I was asked to give a convocation address to the…

总结819

学习目标&#xff1a; 4月&#xff08;复习完高数18讲内容&#xff0c;背诵21篇短文&#xff0c;熟词僻义300词基础词&#xff09; 第二周&#xff1a; 学习内容&#xff1a; 暴力英语&#xff1a;早上背诵《think different》记150词&#xff0c;默写了两篇文章&#xff0c…

HMM-读书笔记

信息提取基础 MM 马卡洛夫链(Markov chain)是处理一类随机过程&#xff0c;这些过程包含最少量的内存&#xff0c;但实际上并不是无记忆的。下面&#xff0c;我们将处理离散随机变量和有限马尔可夫链。令 X1, X2, … , Xn, … 为随机变量序列&#xff0c;它们的值为同样有限字…

R语言算法丨批量查找SNP位点连锁区内对应的QTL以及基因

批量查找SNP位点连锁区内对应的QTL以及基因 如果已知SNP位点的物理位置和其LDblock区间的端点&#xff0c;想要快速找到该区间内的QTL&#xff0c;之后根据参考基因组找到与连锁区域存在交集的基因&#xff0c;最终得到与SNP和QTL相匹配的基因集 通常的做法是在Excel中先对每个…

ASP.NET 记录 HttpRequest HttpResponse HttpServerUtility

纯属个人记录,会有错误 HttpRequest Browser是获取客户端浏览器的信息 Cookies是获取客户端的Cookies QueryString是获取客户端提交的数据 ServerVariables是获取服务器端或客户端的环境变量信息 Browser 语法格式: Request.Browser[“浏览器特性名”] 常见的特性名 名称说…

【Linux】Centos安装mvn命令(maven)

&#x1f341;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; 文章目录一、下载maven包方法一&#xff1a;官…

Flink 优化 (三) --------- 反压处理

目录一、概述1. 反压的理解2. 反压的危害二、定位反压节点1. 利用 Flink Web UI 定位2. 利用 Metrics 定位三、反压的原因及处理1. 查看是否数据倾斜2. 使用火焰图分析3. 分析 GC 情况4. 外部组件交互一、概述 Flink 网络流控及反压的介绍&#xff1a;https://flink-learning.…

[2019.01.24]JNI经验积累

[1 jobject<--->jclass|jstring](1)jobject向上转型jclass|jstring:jclass jcls static_cast<jclass>(jobject);jstring jstr static_cast<jclass>(jobject);(2)jclass|jstring向下转型jobject:默认情况下是自动转换的[2 jstring<--->const char*](1…

(排序6)快速排序(小区间优化,非递归实现)

TIPS 快速排序本质上是一个分治递归的一个排序。快速排序的时间复杂度是NlogN&#xff0c;这是在理想的情况之下&#xff0c;但是它最坏可以到达N^2。决定快速排序的效率是在单趟排序之后这个key最终落在的位置&#xff0c;越落在中间就越接近二分&#xff0c;越接近2分就越接…

手写vuex4源码(六)命名空间实现

一、命名空间使用 在子模块对象中添加 namespaced&#xff1a;true&#xff0c;为模块开启命名空间功能&#xff1b; 开启命名空间功能&#xff0c;相当于为每个模块添加独立的作用域&#xff0c;实现模块间状态和事件的隔离&#xff1b; 二、命名空间实现逻辑 在模块注册阶…

【神经网络】tensorflow实验5--数字图像基础

目录 1. 实验目的 2. 实验内容 3. 实验过程 题目一&#xff1a; ① 代码 ② 实验结果 题目二&#xff1a; ① 代码 ② 实验结果 4. 实验小结&讨论题 1. 实验目的 ①了解数字图像基本属性&#xff1b; ②掌握Pillow图像处理库的基本操作。 2. 实验内容 ①使用Pill…

BGP与OSPF混合组网

如图。R1和R2之间是OSPF Area 0,R23和R4之间是OSPF Area 1,R5和R6之间是OSPF Area2。除了R1和R2之间的cost是100,其余链路的cost都是10. AR1/2/3/4/5/6之间通过Loopback口建立IBGP全互联邻居关系,并且都是AS11520,和外部建立EBGP邻居访问100.100.100.1的网络。(不确定图中…

穿戴规范智能识别系统 yolov7

穿戴规范智能识别系统通过yolov7python网络模型AI深度视觉学习算法&#xff0c;穿戴规范智能识别系统对工厂画面中人员穿戴行为自动识别分析&#xff0c;发现现场人员未按照规定穿戴着装&#xff0c;立即抓拍告警。YOLOv7 的发展方向与当前主流的实时目标检测器不同&#xff0c…

(邱维声)高等代数课程笔记:n 元排列

n 元排列 \quad回顾一下&#xff0c;数域 KKK 上的 nnn 元线性方程组解的情况有几种&#xff1f;前面我们通过对增广矩阵作初等行变换化为阶梯形已经解决了这个问题。 \quad但事实上&#xff0c;化完阶梯形后&#xff0c;这个方程组的求解已经完成的差不多了。换言之&#xff0…

Python 小型项目大全 6~10

六、凯撒密码 原文&#xff1a;http://inventwithpython.com/bigbookpython/project6.html 凯撒密码是朱利叶斯凯撒使用的一种古老的加密算法。它通过将字母在字母表中移动一定的位置来加密字母。我们称移位的长度为密钥。比如&#xff0c;如果密钥是 3&#xff0c;那么A变成D&…

关键词数据分析-搜索词和关键词分析工具

要搜索热门关键词获取&#xff0c;可以采用以下几种方法&#xff1a; 使用百度指数&#xff1a;百度指数是一个实用的工具&#xff0c;可用于查看关键词的热度趋势、搜索量等数据。在百度指数中&#xff0c;您可以输入您要搜索的关键词&#xff0c;并查看近期的相关数据。这可以…

【Unity VR开发】结合VRTK4.0:创建一个按钮(Option Button)

语录&#xff1a; 如同天上降魔主&#xff0c;真是人间太岁神。 前言&#xff1a; 选项按钮是一种提供多项选择选项的方法&#xff0c;其中只有一个按钮可以处于激活状态&#xff0c;激活另一个按钮时将确保组中的所有其他按钮都已停用。我们可以使用嵌套在预制件中的预制件来实…

uniapp页面后退时更改页面内容【uniapp如何区分页面是跳转来的还是后退来的】【伸手党福利】

目录应用场景实现目标分析技术难点解决方法另附&#xff1a;自动登录判断跳转页面ps2 这个案例的实际简单的解决方法应用场景 建立一个自动登录的中间页&#xff0c;如果自动登录&#xff0c;则自动跳转到内部应用。如果自动登录失败&#xff0c;则显示用户名密码输入页。 发现…