当前位置: 首页 > news >正文

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 &#xff1a; 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 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、导入 例子完整的代码效果 总结 需求描述 在应用开发时&#xff0c;我们有很多场景要使用到更换图片的功能&#xff0c;即将原本的图像替换设置成其他的图像&#xff0c;从设备的相册或相机中选择图片或拍…...

数学建模体系

1评价类 主观求权重&#xff1a;层次分析法客观求权重&#xff1a;TOPSIS综合评价&#xff1a;典型相关分析 2预测插值算法拟合多元回归分析时间序列分析、ARCH和garch模型岭回归和lasso回归 3关系相关系数典型相关分析多元回归分析灰色关联分析 4图最短路径&#xff1a;迪杰斯…...

13.7 CentOS 7 环境下大量创建帐号的方法

13.7.1 一些帐号相关的检查工具 pwck pwck 这个指令在检查 /etc/passwd 这个帐号配置文件内的信息&#xff0c;与实际的主文件夹是否存在等信息&#xff0c; 还可以比对 /etc/passwd /etc/shadow 的信息是否一致&#xff0c;另外&#xff0c;如果 /etc/passwd 内的数据字段错…...

HTML5 Canvas(画布)

<canvas>标签定义图形&#xff0c;比如图表和其他图像&#xff0c;你必须用脚本来绘制图形。 在画布上&#xff08; Canvas &#xff09;画一个共红色矩形&#xff0c;渐变矩形&#xff0c;彩色矩形&#xff0c;和一些彩色文字。 什么是 Canvas&#xff1f; 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镜像 构建镜像 概述&#xff1a; Docker 镜像是Docker容器技术中的核心&#xff0c;也是应用打包构建发布的标准格式。…...

JS中常见的模块管理规范梳理

一、CommonJS规范 CommonJS规范是一种用于JavaScript模块化开发的规范&#xff0c;它定义了模块的导入、导出方式和加载机制&#xff0c;主要用在Node开发中。 1. 使用场景 服务器端开发&#xff1a;Node.js是使用CommonJS规范的&#xff0c;因此在服务器端开发中&#xff0…...

3维空间下按平面和圆柱面上排版设计

AR空间中将若干平面窗口排列在指定平面或圆柱体面上 平面排版思路 指定平面方向向量layout_centre ,平面上的一点作为排版版面的中心layout_position float3 layout_position = float3(0,0,-10); float3 layout_centre = float3(0,0,1...

【Spring框架】Spring AOP

目录 什么是AOP&#xff1f;AOP组成Spring AOP 实现步骤Spring AOP实现原理JDK Proxy VS CGLIB 什么是AOP&#xff1f; AOP&#xff08;Aspect Oriented Programming&#xff09;&#xff1a;⾯向切⾯编程&#xff0c;它是⼀种思想&#xff0c;它是对某⼀类事情的集中处理。⽐如…...

寻找旋转排序数组中的最小值——力扣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数据时&#xff0c;有些字段是加密的&#xff0c;如某麦网x-mini-wua x-sgext x-sign x-umt x-utdid等参数&#xff0c;这时候我们需要去分析加密字段的生成。本篇将以采集的角度讲解入门安卓逆向需要掌握的技能、工具。 2、安卓&#xff08;Androi…...

验证码安全志:AIGC+集成环境信息信息检测

目录 知己知彼&#xff0c;黑灰产破解验证码的过程 AIGC加持&#xff0c;防范黑灰产的破解 魔高一丈&#xff0c;黑灰产AIGC突破常规验证码 双重防护&#xff0c;保障验证码安全 黑灰产经常采用批量撞库方式登录用户账号&#xff0c;然后进行违法违规操作。 黑灰产将各种方…...

R-Meta分析教程

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

【3维视觉】3D空间常用算法(点到直线距离、面法线、二面角)

3D空间点到直线的距离 3D空间点到直线的距离 3D空间的曲率 三维空间有三个基本元素&#xff0c;点&#xff0c;线&#xff0c;面。那么曲率是如何定义的呢&#xff1f; 点的曲率&#xff1f; 线的曲率&#xff1f; 面的曲率&#xff1f; 法曲率 设曲面上的曲线在某一点处的切…...

Nodejs 第四章(Npm install 原理)

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

[深度学习] GPU处理能力(TFLOPS/TOPS)

计算能力换算 理论峰值 &#xff1d; GPU芯片数量GPU Boost主频核心数量*单个时钟周期内能处理的浮点计算次数 只不过在GPU里单精度和双精度的浮点计算能力需要分开计算&#xff0c;以最新的Tesla P100为例&#xff1a; 双精度理论峰值 &#xff1d; FP64 Cores &#xff0a;…...

js:获取浏览器默认语言

实现代码 navigator.language zh-CN参考文章 [javascript] js如何获取浏览器的语言...

【U8+】用友U8重新注册加密锁,提示:写卡失败,请重新配置客户端控件。

【问题描述】 用友U8软件重新安装后&#xff0c;需要重新注册加密锁激活软件。 注册反馈提示&#xff1a;产品注册失败。 原因&#xff08;1&#xff09;&#xff1a;写卡失败&#xff0c;请重新配置客户端控件。 【解决方法】 1、打开控制面板&#xff0c;网络和 Internet&a…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

MMaDA: Multimodal Large Diffusion Language Models

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

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

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

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...