leetcode原题 路径总和 I II III(递归实现)
路径总和 I :
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。
要点:判断是否存在满足条件的路径,只需返回true or false。
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
解题思路:
每遍历一个节点,就从targetsum中减去当前节点的值,当遍历到叶子节点时,如果targetsum=0,说明存在该路径,返回true。反之,返回false
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if(root==nullptr) return false;targetSum-=root->val;if(root->left==nullptr&&root->right==nullptr){return targetSum==0;}//左子树和右子树有一个满足就可以,所以用||的关系return hasPathSum(root->left,targetSum)||hasPathSum(root->right,targetSum);}
};
路径总和 II:
给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
要点:返回所有满足题意的路径,必须是从根节点开始,叶子节点结束。
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
解题思路:
添加一个临时数组,用来存放当前遍历到的节点走过的路径。其他的与第一题相同,找到符合题意的路径,就将临时数组存放到结果数组中,若不符合条件,需回退,注意回退时需要将将一个放到临时数组中的节点删掉。
class Solution {
public:vector<vector<int>> res;//所有路径vector<int> temp;//当前路径void dfs(TreeNode* root, int targetSum){if(root==nullptr) return;temp.push_back(root->val);//当前节点放入到temp中targetSum-=root->val;//从总和中减去//若遇到叶子节点,需判断目标值是否已经为0if(root->left==nullptr&&root->right==nullptr){//目标值=0,说明当前路径符合题意,temp放到res中if(targetSum==0){res.push_back(temp);}}//递归dfs(root->left,targetSum);dfs(root->right,targetSum);//不符合题意,将当前节点从路径中删掉temp.pop_back();}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {dfs(root,targetSum);return res;}
};
路径总和 III:
给定一个二叉树的根节点 root
,和一个整数 targetSum
,求该二叉树里节点值之和等于 targetSum
的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
要点:返回的是所有符合题意的路径总条数,与第二题不一样的是,可以不是从根节点开始,也不需要在叶子节点结束。
输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
解释:和等于 8 的路径有 3 条,如图所示。
解题思路:
相当于是递归套递归,构建一个找路径函数,遍历以当前节点为起始的路径中,是否存在符合题意的路径,然后再在原函数递归到每一个节点,使每一个节点都为起始节点进行找符合题意的路径。
class Solution {
public:int res=0;int pathSum(TreeNode* root, int targetSum) {if(root==nullptr) return res;find_path(root,targetSum);//以当前的root节点为起始节点,找路径pathSum(root->left,targetSum);//递归当前根节点的左子树上的节点pathSum(root->right,targetSum);//递归当前根节点的右子树上的节点return res;}//找路径函数void find_path(TreeNode* root,long targetSum){if(root==nullptr) return;targetSum -= root->val;if(targetSum==0)//只要targetsum=0,说明存在一条路径,那么res++{res+=1;}find_path(root->left,targetSum);find_path(root->right,targetSum);}
};
相关文章:

leetcode原题 路径总和 I II III(递归实现)
路径总和 I : 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。…...

【css】css设置表格样式-边框线合并
<style> table, td, th {border: 1px solid black;//设置边框线 }table {width: 100%; }td {text-align: center;//设置文本居中 } </style> </head> <body><table><tr><th>Firstname</th><th>Lastname</th><t…...

使用Flutter的image_picker插件实现设备的相册的访问和拍照
文章目录 需求描述Flutter插件image_picker的介绍使用步骤1、添加依赖2、导入 例子完整的代码效果 总结 需求描述 在应用开发时,我们有很多场景要使用到更换图片的功能,即将原本的图像替换设置成其他的图像,从设备的相册或相机中选择图片或拍…...
数学建模体系
1评价类 主观求权重:层次分析法客观求权重:TOPSIS综合评价:典型相关分析 2预测插值算法拟合多元回归分析时间序列分析、ARCH和garch模型岭回归和lasso回归 3关系相关系数典型相关分析多元回归分析灰色关联分析 4图最短路径:迪杰斯…...

13.7 CentOS 7 环境下大量创建帐号的方法
13.7.1 一些帐号相关的检查工具 pwck pwck 这个指令在检查 /etc/passwd 这个帐号配置文件内的信息,与实际的主文件夹是否存在等信息, 还可以比对 /etc/passwd /etc/shadow 的信息是否一致,另外,如果 /etc/passwd 内的数据字段错…...

HTML5 Canvas(画布)
<canvas>标签定义图形,比如图表和其他图像,你必须用脚本来绘制图形。 在画布上( Canvas )画一个共红色矩形,渐变矩形,彩色矩形,和一些彩色文字。 什么是 Canvas? HTML5<c…...
io的异常处理以及properties
try(流对象的创建) { 对象的处理逻辑} catch(IOException e) { 异常的处理逻辑} public static void test4(){try(FileWriter fwnew FileWriter("a.txt",true); ){char[] cbuf{a};//写入一个字符串组fw.write(cbuf);}catch(IOException e){e.printStackTrace();}}上面…...

Linux下基于Dockerfile构建镜像应用(1)
目录 基于已有容器创建镜像 Dockerfile构建SSHD镜像 构建镜像 测试容器 可以登陆 Dockerfile构建httpd镜像 构建镜像 测试容器 Dockerfile构建nginx镜像 构建镜像 概述: Docker 镜像是Docker容器技术中的核心,也是应用打包构建发布的标准格式。…...
JS中常见的模块管理规范梳理
一、CommonJS规范 CommonJS规范是一种用于JavaScript模块化开发的规范,它定义了模块的导入、导出方式和加载机制,主要用在Node开发中。 1. 使用场景 服务器端开发:Node.js是使用CommonJS规范的,因此在服务器端开发中࿰…...
3维空间下按平面和圆柱面上排版设计
AR空间中将若干平面窗口排列在指定平面或圆柱体面上 平面排版思路 指定平面方向向量layout_centre ,平面上的一点作为排版版面的中心layout_position float3 layout_position = float3(0,0,-10); float3 layout_centre = float3(0,0,1...

【Spring框架】Spring AOP
目录 什么是AOP?AOP组成Spring AOP 实现步骤Spring AOP实现原理JDK Proxy VS CGLIB 什么是AOP? AOP(Aspect Oriented Programming):⾯向切⾯编程,它是⼀种思想,它是对某⼀类事情的集中处理。⽐如…...

寻找旋转排序数组中的最小值——力扣153
文章目录 题目描述解法 二分法 题目描述 解法 二分法 int findMin(vector<int>& nums){int l0, rnums.size()-1;while(l<r){int mid (lr)/2;if(nums[mid]<nums[r]) rmid;else lmid1;}return nums[l];}...

安卓逆向 - 基础入门教程
一、引言 1、我们在采集app数据时,有些字段是加密的,如某麦网x-mini-wua x-sgext x-sign x-umt x-utdid等参数,这时候我们需要去分析加密字段的生成。本篇将以采集的角度讲解入门安卓逆向需要掌握的技能、工具。 2、安卓(Androi…...

验证码安全志:AIGC+集成环境信息信息检测
目录 知己知彼,黑灰产破解验证码的过程 AIGC加持,防范黑灰产的破解 魔高一丈,黑灰产AIGC突破常规验证码 双重防护,保障验证码安全 黑灰产经常采用批量撞库方式登录用户账号,然后进行违法违规操作。 黑灰产将各种方…...

R-Meta分析教程
详情点击链接:R-Meta模型教程 一:Meta分析的选题与文献计量分析CiteSpace应用 1、Meta分析的选题与文献检索 1)什么是Meta分析? 2)Meta分析的选题策略 3)文献检索数据库 4)精确检索策略,如何检索全、检索准 5)文献的管理与…...

【3维视觉】3D空间常用算法(点到直线距离、面法线、二面角)
3D空间点到直线的距离 3D空间点到直线的距离 3D空间的曲率 三维空间有三个基本元素,点,线,面。那么曲率是如何定义的呢? 点的曲率? 线的曲率? 面的曲率? 法曲率 设曲面上的曲线在某一点处的切…...

Nodejs 第四章(Npm install 原理)
在执行npm install 的时候发生了什么? 首先安装的依赖都会存放在根目录的node_modules,默认采用扁平化的方式安装,并且排序规则.bin第一个然后系列,再然后按照首字母排序abcd等,并且使用的算法是广度优先遍历,在遍历依…...

[深度学习] GPU处理能力(TFLOPS/TOPS)
计算能力换算 理论峰值 = GPU芯片数量GPU Boost主频核心数量*单个时钟周期内能处理的浮点计算次数 只不过在GPU里单精度和双精度的浮点计算能力需要分开计算,以最新的Tesla P100为例: 双精度理论峰值 = FP64 Cores *…...
js:获取浏览器默认语言
实现代码 navigator.language zh-CN参考文章 [javascript] js如何获取浏览器的语言...

【U8+】用友U8重新注册加密锁,提示:写卡失败,请重新配置客户端控件。
【问题描述】 用友U8软件重新安装后,需要重新注册加密锁激活软件。 注册反馈提示:产品注册失败。 原因(1):写卡失败,请重新配置客户端控件。 【解决方法】 1、打开控制面板,网络和 Internet&a…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...