【题解】二叉树中和为某一值的路径(一)
二叉树中和为某一值的路径(一)
题目链接:二叉树中和为某一值的路径(一)
解题思路1:递归
我们或许想记录下每一条从根节点到叶子节点的路径,计算出该条路径的和,但此种思路用递归稍麻烦,我们可以试着把和转换为差,从根节点开始,sum就减去根节点的值,如果到叶子节点,减为0了,那就证明此路径满足要求
递归结束条件:节点为空,意味着已经走过了叶子节点,返回;每当检查到某节点没有子节点,则说明该节点为叶子节点,如果此时sum的值减去该节点的值刚好为0,则说明找到了路径
返回值:将子问题中是否有复合新目标值的路径层层往上返回
本级任务:每一层需要检查是否到了叶子节点,如果没有则递归进入子节点,同时更新sum值减掉本层的节点值
代码如下:
bool hasPathSum(TreeNode* root, int sum) {if(root == nullptr) return false;if(root->left==nullptr && root->right==nullptr && sum-root->val==0) return true;return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);}
解题思路2:非递归,栈+DFS
我们上面是一步一步减去当前root的值,看最后root为空时,sum的值是否为0,采用递归实现,在此,我们采用走一步加上一步当前节点的值,看最后加和是否满足sum,我们采用栈和深度优先搜索来实现
深度优先搜索:深度优先搜索一般用于树或者图的遍历,其他有分支也适用,它是从初始点开始,一直沿着同一个分支遍历,直到该分支结束,然后回溯到上一级继续沿着一个分支走到底,如此往复,直到所有的节点都有被访问到
具体步骤:
首先检查空节点,若为空树,则返回
使用栈嵌套pair,first记录节点,second记录经过的节点的值的和。根节点及根节点的值先进栈。
遍历的时候判断是否是叶子节点,且和是否等于sum,是则返回true
如果节点有子节点,就入栈,并更新路径和
如果遍历结束也没有找到规定的路径,则返回false,该二叉树中没有符合条件的路径
当到达当前节点时,second中的值已经加过该节点的值了
代码如下:
bool hasPathSum(TreeNode* root, int sum) {if (root == nullptr) return false;//栈辅助深度优先遍历,并记录到相应节点的路径和stack<pair<TreeNode*, int>> s;//根节点先入栈s.push({root, root->val});while (!s.empty()) {auto temp = s.top();s.pop();//是叶子节点,且路径和等于sumif (temp.first->left == nullptr && temp.first->right == nullptr &&temp.second == sum)return true;//左节点入栈if (temp.first->left != nullptr)s.push({temp.first->left, temp.first->left->val + temp.second});//右节点入栈if (temp.first->right != nullptr)s.push({temp.first->right, temp.first->right->val + temp.second});}return false;}
相关文章:
【题解】二叉树中和为某一值的路径(一)
二叉树中和为某一值的路径(一) 题目链接:二叉树中和为某一值的路径(一) 解题思路1:递归 我们或许想记录下每一条从根节点到叶子节点的路径,计算出该条路径的和,但此种思路用递归稍麻烦,我们可以试着把和转换为差&am…...
css中变量和使用变量和运算
变量: 语法:--css变量名:值; --view-theme: #1a99fb; css使用变量: 语法:属性名:var( --css变量名 ); color: var(--view-theme); css运算: 语法:属性名…...
数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表
线性表 定义 一个最简单,最基本的数据结构。一个线性表由多个相同类型的元素穿在一次,并且每一个元素都一个前驱(前一个元素)和后继(后一个元素)。 线性表的类型 常见的类型:数组、栈、队列…...
成瘾机制中微生物群的神秘角色
谷禾健康 成瘾是一种大脑疾病,受害者无法控制地对某种物质或行为产生强烈的依赖和渴求,尽管这种行为会产生有害的后果。成瘾包括一系列物质滥用障碍,例如药物、酒精、香烟,过度饮食。近年来,吸毒成瘾急剧上升ÿ…...
arm安装docker与docker-copose
一、银河麒麟Arm64安装docker 1、docker 安装包地址: https://download.docker.com/linux/static/stable 2、解压,然后将docker目录下文件拷贝到/usr/bin里 tar -xf docker-18.09.3.tgz mv docker/* /usr/bin/ 3、准备 docker.service系统配置文件 &…...
9.文件基本操作
第四章 文件管理 9.文件基本操作 “打开文件和关闭文件”与平常鼠标双击打开文件和点击“X”关闭文件是有所不同的。 操作系统在处理open系统调用时主要做了以下两件事情,①根据我们提供的文件存放路径在外存当中找到这个目录对应的目录表&#x…...
【Java】Spring——Bean对象的作用域和生命周期
文章目录 前言一、引出Bean对象的作用域1.普通变量的作用域2.Bean对象的作用域 二、Bean对象的作用域1.Bean对象的6种作用域2.设置Bean对象的作用域 三、Bean对象的生命周期总结 前言 本人是一个普通程序猿!分享一点自己的见解,如果有错误的地方欢迎各位大佬莅临指导,如果你也…...
数字孪生助力智慧水务:科技创新赋能水资源保护
智慧水务中,数字孪生有着深远的作用,正引领着水资源管理和环境保护的创新变革。随着城市化和工业化的不断推进,水资源的可持续利用和管理愈发显得重要,而数字孪生技术为解决这一挑战提供了独特的解决方案。 数字孪生技术…...
css 实现文字横向循环滚动
实现效果 思路 ## 直接上代码,html部分 //我这里是用的uniapp <view class"weather_info_wrap"><view class"weather_info">当前多云,今晚8点转晴,明天有雨,温度32摄氏度。</view><view class&qu…...
VuePress 数学公式支持
前言 博主在为 VuePress1.0 博客添加数学公式支持过程中遇到如下问题 问题一 在配置诸如 markdown-it-texmath,markdown-it-katex,markdown-it-mathjax3 这些插件后遇到 Error: Dynamic require of "XXX" is not supported 问题二 配置插件 vuepress-plugin-ma…...
stm32控制蜂鸣器源代码(附带proteus线路图)
说明: 1 PB0输出0时,蜂鸣器发生; 2 蜂鸣器电阻值如果太大会导致电流太小,发不出声音; 3蜂鸣器额定电压需要设置得低一点,可以是2V,但不能高于3V,这更右上角的电阻值有关系&#x…...
selinux
一、selinux的说明 二、selinux的工作原理 三、selinux的启动、关闭与查看 Enforcing和permissive都是临时的,重启还是依据配置文件中,禁用selinux,修改配置文件: 之后重启生效 四、selinux对linux服务的影响...
使用opencv4.7.0部署yolov5
yolov5原理和部署原理就不说了,想了解的可以看看这篇部署原理文章 #include <fstream> #include <sstream> #include <iostream> #include <opencv2/dnn.hpp> #include <opencv2/imgproc.hpp> #include <opencv2/highgui.hpp>/…...
Python - 协程基本使用详解【demo】
一. 前言 协程(Coroutine)是一种轻量级的线程,也被称为用户级线程或绿色线程。它是一种用户态的上下文切换方式,比内核态的线程切换更为轻量级,能够高效的支持大量并发操作。 2. 使用协程的好处 Python 中的协程是通…...
Android MVVM架构模式,详详详细学习
MVVM(Model-View-ViewModel) 是一种基于数据绑定的架构模式,用于设计和组织应用程序的代码结构。它将应用程序分为三个主要部分:Model(模型)、View(视图)和ViewModel(视…...
亿赛通电子文档安全管理系统 RCE漏洞复现
0x01 产品简介 亿赛通电子文档安全管理系统(简称:CDG)是一款电子文档安全加密软件,该系统利用驱动层透明加密技术,通过对电子文档的加密保护,防止内部员工泄密和外部人员非法窃取企业核心重要数据资产&…...
星际争霸之小霸王之小蜜蜂(三)--重构模块
目录 前言 一、为什么要重构模块 二、创建game_functions 三、创建update_screen() 四、修改alien_invasion模块 五、课后思考 总结 前言 前两天我们已经成功创建了窗口,并将小蜜蜂放在窗口的最下方中间位置,本来以为今天将学习控制小蜜蜂,结…...
JS的解析与Js2Py使用
JS的解析与Js2Py使用 JS的解析事件监听器搜索关键字请求关联JS文件 Js2PyJs2Py的简单使用安装Js2Py执行JavaScript代码调用JavaScript函数 Js2Py的应用示例创建JavaScript文件使用JavaScript JS的解析 在一个网站中,登录密码通常是会进行加密操作的,那么…...
Spring Bean的生命周期总结(包含面试题)
目录 一、Bean的初始化过程 1. 加载Spring Bean 2. 解析Bean的定义 3. Bean属性定义 4. BeanFactoryPostProcessor 扩展接口 5. 实例化Bean对象 6. Aware感知 7. 初始化方法 8. 后置处理 9. destroy 销毁 二、Bean的单例与多例模式 2.1 单例模式(Sin…...
SpringjDBCTemplate_spring25
1、首先导入两个包,里面有模板 2、transtion事务 jDbc操作对象,底层默认的是事务: 3、我们java一般对实体类进行操作。 4、第一步写好坐标。 创建一个Account表 数据修改用update 数据进去了...
设计模式——桥接模式
引用 桥我们大家都熟悉,顾名思义就是用来将河的两岸联系起来的。而此处的桥是用来将两个独立的结构联系起来,而这两个被联系起来的结构可以独立的变化,所有其他的理解只要建立在这个层面上就会比较容易。 基本介绍 桥接模式(Br…...
改进YOLO系列:2.添加ShuffleAttention注意力机制
添加ShuffleAttention注意力机制 1. ShuffleAttention注意力机制论文2. ShuffleAttention注意力机制原理3. ShuffleAttention注意力机制的配置3.1common.py配置3.2yolo.py配置3.3yaml文件配置1. ShuffleAttention注意力机制论文 论文题目:SA-NET: SHUFFLE ATTENTION …...
利用Opencv实现人像迁移
前言: Hello大家好,我是Dream。 今天来学习一下如何使用Opencv实现人像迁移,欢迎大家一起参与探讨交流~ 本文目录: 一、实验要求二、实验环境三、实验原理及操作1.照片准备2.图像增强3.实现美颜功能4.背景虚化5.图像二值化处理6.人…...
Lnton羚通算法算力云平台在环境配置时 OpenCV 无法显示图像是什么原因?
问题: cv2.imshow 显示图像时报错,无法显示图像 0%| | 0/1 [00:00<…...
【JavaEE进阶】MyBatis的创建及使用
文章目录 一. MyBatis简介二. MyBatis 使用1. 数据库和数据表的创建2. 创建Mybatis项目2.1 添加MyBatis框架支持2.2 设置MyBatis配置信息 3. MyBatis开发流程4. MyBatis查询数据库测试 三. MyBatis 流程1. MyBatis 查询数据库流程2. MyBatis 框架交互流程图 一. MyBatis简介 M…...
职业学院物联网实训室建设方案
一、概述 1.1专业背景 物联网(Internet of Things)被称为继计算机、互联网之后世界信息产业第三次浪潮,它并非一个全新的技术领域,而是现代信息技术发展到一定阶段后出现的一种聚合性应用与技术提升,是随着传感网、通…...
3 个 ChatGPT 插件您需要立即下载3 ChatGPT Extensions You need to Download Immediately
在16世纪,西班牙探险家皮萨罗带领约200名西班牙士兵和37匹马进入了印加帝国。尽管印加帝国的军队数量达到了数万,其中包括5,000名精锐步兵和3,000名弓箭手,他们装备有大刀、长矛和弓箭等传统武器。但皮萨罗的军队中有100名火枪手,…...
屏蔽socket 实例化时,握手阶段报错信息WebSocket connection to ‘***‘ failed
事情起因是这样的: 我们网站是需要socket链接实行实时推送服务,有恶意竞争对手通过抓包或者断网,获取到了我们的socket链接地址,那么他就可以通过java写一个脚本无限链接这个socket地址。形成dos攻击。使socket服务器资源耗尽&…...
单发多框检测(SSD)【动手学深度学习】
单发多框检测模型主要由一个基础网络块和若干多尺度特征块串联而成。基本网络用于从输入图像中提取特征,可以使用深度卷积神经网络,原论文中选用了在分类层之前阶段的VGG,现在也常用ResNet替代。 我们可以设计基础网络,使它输出的高和宽较大,这样基于该特征图生成的锚框数…...
“RFID与光伏板的完美融合:探索能源科技的新时代!“
随着科技的不断发展,人类创造出了许多令人惊叹的发明。其中,RFID(Radio Frequency Identification)技术的应用在各个领域日益广泛。最近的研究表明,将RFID技术应用于光伏板领域,不仅可以提高光伏板的效率&a…...
算法leetcode|71. 简化路径(rust重拳出击)
文章目录 71. 简化路径:样例 1:样例 2:样例 3:样例 4:提示: 分析:题解:rust:go:c:python:java: 71. 简化路径:…...
网络技术Vlan技术STP(第一课)
一 Vlan技术的学习 对命令的增删改查 #### 1)创建vlan[SW1]vlan 2 [2-4094] 创建vlan[SW1]vlan batch 10 20 30 创建多个不连续的vlan[SW1]display vlan 查看vlan信息[SW1]vlan batch 50 to 60创建多个连续的vlan[SW1]vlan2[SW1-vlan2]description caiwu添加描述信…...
SpringBoo t+ Vue 微人事 (十一)
职位修改操作 在对话框里面做编辑的操作 添加对话框 <el-dialogtitle"修改职位":visible.sync"dialogVisible"width"30%"><div><el-tag>职位名称</el-tag><el-input size"small" class"updatePosIn…...
自动驾驶卡车量产-第一章-用户需求
1、中国干线物流行业现状 万亿级市场,规模巨大。由中重卡承运的干线运输占到整体公路货运市场的82%,全国中重卡保有量约730 万台1,市场规模达4.6 万亿元1,体量全球第一,超过同城物流及乘用出租市场规模之和。同样&…...
Nginx 配置文件的完整指南 (一)
文章目录 一、简介1.1 配置文件一览 二、全局配置2.0 user2.1 worker_processes2.2 events模块2.3 http模块 三、server模块3.1 listen3.2 server_name3.3 location:请求处理位置 Nginx 配置文件的完整指南 (二) 一、简介 Nginx是一款高性能的Web服务器和反向代理服…...
css3+js 画出爱心特效
要使用CSS3和JavaScript绘制爱心特效,可以使用CSS3的动画和过渡效果来创建爱心的形状,并使用JavaScript来控制动画的触发和交互。以下是一个简单的示例代码: HTML: <div class"heart"></div> <button onclick&quo…...
蔚来李斌卖手机:安卓系统,苹果售价,一年一发
作者 | Amy 编辑 | 德新 车圈大佬的玩法真让人寻不着套路! 苹果的库克和小米的雷布斯,甚至是FF贾老板准备许久,都想分一块新能源车的蛋糕,蔚来李斌却反手进军手机界,从宣布造手机到手机入网仅仅隔了一年。 近期&a…...
0008__浏览器层面缓存 Etag If-None-Match等详解
浏览器层面缓存 Etag & If-None-Match等详解_if-none-match:_shadow_zed的博客-CSDN博客...
Idea 快捷键整理
Idea快捷键和自动代码补全汇总 idea快捷键汇总 Ctrl 快捷键说明Ctrl F在当前文件进行文本查找 (必备)Ctrl R在当前文件进行文本替换 (必备)Ctrl Z撤销 (必备)Ctrl Y删除光标所在行 或 删除选中的行 &am…...
管理类联考——逻辑——真题篇——按知识分类——汇总篇——一、形式逻辑——假言——第一节 充分条件
文章目录 第一节 充分条件假言命题-那么,就,则真题(2013-29)-假言-充分假言-那么,就,则-变形推理真题(2014-44)-假言-充分假言-那么,就,则-(1)建模-“那么/就/则”-前推后真题(2018-37)-假言-充分假言-那么,就,则-(1)建模-“那么/就/则”-前推后;-(2)A→…...
LSTM模型
目录 LSTM模型 LSTM结构图 LSTM的核心思想 细胞状态 遗忘门 输入门 输出门 RNN模型 LRNN LSTM模型 什么是LSTM模型 LSTM (Long Short-Term Memory)也称长短时记忆结构,它是传统RNN的变体,与经典RNN相比能够有效捕捉长序列之间的语义关联,缓解梯度消失或爆炸现象.同时LS…...
抢红包小程序
抢红包小程序 红包大战 # urls.pyfrom django.urls import pathfrom . import viewsurlpatterns [ path(login/, views.login, namelogin), path(create_red_packet/, views.create_red_packet, namecreate_red_packet), path(join_red_packet/<int:red_packet_id…...
UVA 10006 埃氏筛法+快速幂
本题目使用费马定理时,我随机定义了10个数字,循环用费马小定理判断,数组中的值不用和我的相同,随机即可。 #include <iostream> using namespace std; typedef unsigned long long ll; bool isPrime[65007]; ll a[10]; voi…...
C++--红黑树
1.什么是红黑树 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因…...
Unity 找不到 Navigation 组件的解决
当我们想利用unity 里面的Navigation 组件来实现我们的物体的自动导航时,有时竟然会发现我们的菜单栏里面找不到 该组件 这时我们应该怎么办? 请确保你的项目中已经导入了Unity的AI模块。要导入该模块,请打开"Project Settings"&am…...
【js】时间和时间戳转换、日期格式化
1、时间戳转换日期方法 (格式:2023-08-17) function timestampToDate(date) {var date new Date(date);var YY date.getFullYear() -;var MM (date.getMonth() 1 < 10 ? 0 (date.getMonth() 1) : date.getMonth() 1) -;var DD …...
glog体验第一天(0)glog介绍和安装
在Ubuntu上安装glog,可以按照以下步骤进行操作: 打开终端,使用以下命令更新本地软件包列表: sudo apt-get update然后,使用以下命令安装glog库及其开发工具: sudo apt-get install -y libgoogle-glog-de…...
Android 13像Settings一样获取SIM卡信息
一.背景 由于客户定制的Settings里面需要获取到SIM卡信息,所以需要实现此功能。 目录 一.背景 二.前提条件 三.调用api 二.前提条件 首先应用肯定要是系统应用,并且导入framework.jar包,具体可以参考: Android 应用自动开启辅助(无障碍)功能并使用辅助(无障碍)功能_…...
Can‘t find end of central directory : is this a zip file ? at XMLHttpRequest
导出woed出现这个报错,原因其实很简单,路径写错了, 这个word首先必须是docx格式,然后必须放在public文件包下 如果放在public文件包下还没有用,则放在public包下 参考帖子: https://www.cnblogs.com/hejun26/p/13647927.html...
基于SpringBoot+Thymeleaf仓库管理系统
✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景介绍: 随着信息技术的快速发…...