图解LeetCode——剑指 Offer 34. 二叉树中和为某一值的路径
一、题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。
二、示例
2.1> 示例 1:
【输入】root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
【输出】[[5,4,11,2],[5,8,4,5]]
2.2> 示例 2:
【输入】root = [1,2,3], targetSum = 5
【输出】[]
2.3> 示例 3:
【输入】root = [1,2], targetSum = 0
【输出】[]
提示:
- 树中节点总数在范围
[0, 5000] -1000<= Node.val <=1000-1000<= targetSum <=1000
三、解题思路
根据题目要求,我们需要寻找N条从根路径到叶子节点的路径,并要求满足该路径节点之和等于targetSum;既然涉及到二叉树节点遍历,常用的就是深度优先算法和广度优先算法,那么由于本题涉及从根路径到叶子节点的路径,那么我们可以采用深度优先算法+ 前序遍历对这道题进行解答。
其实本题的一个难点就是如何去拼装最终结果List<List<Integer>> result,那么既然是需要获得满足条件的路径节点值的集合,我们就可以创建一个变量LinkedList<Integer> path,用于记录当前所经过的节点值。那么当我们从根节点遍历到叶子节点之后,会有如下两种情况:
【情况1】所有节点总和正好等于
targetSum,那么我们通过复制path,然后保存到result中即可。如果还有其他树节点需要遍历,逐一回溯path末尾节点val值。
【情况2】所有节点总和不等于targetSum,如果还有其他树节点需要遍历,逐一回溯path末尾节点val值。
需要注意的是,当我们确认某一条路径等于targetSum之后,我们需要“复制”该路径(即:通过new LinkedList(path))否则路径就会随着回溯操作而发生变化了。上面就是具体的解题思路,下面我们还是以输入:root = [5,4,8,11,null,13,4,7,2,null,null,5], targetSum = 22为例,看一下具体的操作过程是怎么样的。请见下图所示:

四、代码实现
class Solution {List<List<Integer>> result;LinkedList<Integer> path;public List<List<Integer>> pathSum(TreeNode root, int target) {result = new LinkedList();path = new LinkedList();dfs(root, target);return result;}public void dfs(TreeNode node, int value) {if (node == null) return;path.addLast(node.val);if (node.val == value && node.left == null && node.right == null) result.add(new LinkedList(path));dfs(node.left, value - node.val);dfs(node.right, value - node.val);path.removeLast(); // 回溯}
}

今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」
相关文章:
图解LeetCode——剑指 Offer 34. 二叉树中和为某一值的路径
一、题目 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。 二、示例 2.1> 示例 1: 【输入】root [5,4,8,11,null,13,4,7,2,null,null,5,1], t…...
使用Python免费试用最新Openai API
一、背景介绍 3月2日凌晨,OpenAI放出了真正的ChatGPT API,不是背后的GPT-3.5大模型,是ChatGPT的本体模型!ChatGPT API价格为1k tokens/$0.002,等于每输出100万个单词,价格才2.7美金(约18元人民…...
04、启动 SVN 服务器端程序
启动 SVN 服务器端程序1 概述2 用命令行单项目启动2.1 采用 svnserve 命令2.2 验证服务是否启动2.3 命令行方式的缺陷3 注册Windows服务3.1 注册服务的命令3.2 命令说明3.3 启动服务1 概述 SVN 服务器和 Tomcat 服务器,Nexus 服务器一样, 必须处于运行状态才能响应…...
jsp船舶引航计费网站Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 JSP船舶引航计费网站是一套完善的java web信息管理系统,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发,数据库为Mysql5.0&…...
Allegro如何画半圆形的线操作指导
Allegro如何画半圆形的线操作指导 在用Allegro设计PCB的时候,在某些应用场合会需要画半圆形,如下图 如何画半圆形,具体操作如下 点击Add点击Arc w/Radius...
【强烈建议收藏:MySQL面试必问系列之SQL语句执行专题】
一.知识回顾 之前的文章我们一起学习了MySQL面试必问系列之事务专题、锁专题,没有学习的小伙伴可以直接通过该链接地址直接访问,MYSQL你真的了解吗专栏的文章,接下来我们就一起来学习一下MySQL中SQL语句的执行流程,看看你掌握的怎…...
详解Linux下的环境变量以及C++库文件和头文件、python库的配置
目录 Linux环境变量配置基本步骤 1.查看环境变量 2.设置环境变量 3.永久性设置环境变量 4.使用环境变量 C 库文件和头文件环境变量配置 1.配置so库文件的环境变量 2.配置头文件的环境变量 Python库环境变量配置 Linux配置执行文件环境变量 我们都习惯在Windows 上配置…...
企业级分布式数据库 - GaussDB介绍
目录 什么是GaussDB 简介 应用场景 产品架构 产品优势 安全 责任共担 身份认证与访问控制 数据保护技术 审计与日志 监控安全风险 故障恢复 认证证书 GaussDB与其他服务的关系 约束与限制 计费模式 什么是GaussDB …...
Linux I2C 驱动实验
目录 一、Linux I2C 驱动简介 1、I2C 总线驱动 2、I2C 设备驱动 1、 i2c_client 结构体 2、 i2c_driver 结构体 二、硬件分析 三、设备树编写 1、pinctrl_i2c1 2、在 i2c1 节点追加 ap3216c 子节点 3、验证 四、 代码编写 1、makefile 2、ap3216c.h 3、ap3216c.c …...
DC-DC模块电源隔离直流升压高压稳压输出5v12v24v转60v100v110v150v220v250v300v400v500v
特点效率高达80%以上1*1英寸标准封装单电压输出稳压输出工作温度: -40℃~85℃阻燃封装,满足UL94-V0 要求温度特性好可直接焊在PCB 上应用HRB 0.2~10W 系列模块电源是一种DC-DC升压变换器。该模块电源的输入电压分为:4.5~9V、9~18V、及18~36VDC标准&#…...
EF有几种模式,EF的三种模式分别是什么?
EF有几种模式,EF的三种模式分别是什么? 第一种:DataBase First DataBase First传统的表驱动方式创建EDM,然后通过EDM生成模型和数据层代码。除生成实体模型和自跟踪实现模型,还支持生成轻型DbContext。 解释…...
数据可视化展示:打工人常见职业病,颈腰椎病占比最高达66.51%
身体健康才是一切的根本。只有身体健健康康才能更好的去享受世间的美好,无论是谁都应当注重身体健康,而不是无度的挥霍它! 良好的身体,释放给工作,健壮的体魄,享受美好生活,良好的心态ÿ…...
【食品图像识别】Large Scale Visual Food Recognition
1 引言 视觉智能部与中科院计算所于2020-2021年度展开了《细粒度菜品图像识别和检索》科研课题合作,本文系双方联合在IEEE T-PAMI2023发布论文《Large Scale Visual Food Recognition》 (Weiqing Min, Zhiling Wang, Yuxin Liu, Mengjiang Luo, Liping Kang, Xiaom…...
RAN-in-the-Cloud:为 5G RAN 提供云经济性
RAN-in-the-Cloud:为 5G RAN 提供云经济性 5G 部署在全球范围内一直在加速。 许多电信运营商已经推出了5G服务并正在快速扩张。 除了电信运营商之外,企业也对使用 5G 建立私有网络产生了浓厚的兴趣,这些私有网络利用了更高的带宽、更低的延迟…...
vector、list、queue
引用:windows程序员面试指南 vector vector 类似于C语言中的数组 vector 支持随机访问,访问某个元素的时间复杂度 O(1) vector 插入和删除元素效率较低,时间复杂度O(n) vector 是连续存储,没有内存碎片,空间利用率高…...
操作系统面经
进程与线程区别 1.进程是资源分配的最小单位,线程是程序执行的最小单位(资源调度的最小单位) 2.进程有自己的独立地址空间,每启动一个进程,系统就会为它分配地址空间,建立数据表来维护代码段、堆栈段和数…...
一天约了4个面试,复盘一下面试题和薪资福利
除了最新的面经分享,还有字节大佬的求职面试答疑,告诉你关键问题是什么?少走弯路。**另外本文也汇总了6份大厂面试题:字节、腾讯、小米、腾讯云、滴滴、小米游戏。**希望对大家有帮助。 前言 昨天我的交流群里,有位宝…...
详解单链表(内有精美图示哦)
全文目录引言链表链表的定义与结构链表的分类单链表的实现及对数据的操作单链表的创建与销毁创建销毁单链表的打印单链表的头插与头删头插头删单链表的尾插与尾删尾插尾删单链表的查找单链表在pos位置后插入/删除插入删除单链表在pos位置插入/删除插入删除总结引言 在上一篇文…...
csdn文章导航
这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…...
【Spring】掌握 Spring Validation 数据校验
个人简介:Java领域新星创作者;阿里云技术博主、星级博主、专家博主;正在Java学习的路上摸爬滚打,记录学习的过程~ 个人主页:.29.的博客 学习社区:进去逛一逛~ Spring Validation 数据校验一、什么是 Spring…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
动态规划-1035.不相交的线-力扣(LeetCode)
一、题目解析 光看题目要求和例图,感觉这题好麻烦,直线不能相交啊,每个数字只属于一条连线啊等等,但我们结合题目所给的信息和例图的内容,这不就是最长公共子序列吗?,我们把最长公共子序列连线起…...
RabbitMQ 各类交换机
为什么要用交换机? 交换机用来路由消息。如果直发队列,这个消息就被处理消失了,那别的队列也需要这个消息怎么办?那就要用到交换机 交换机类型 1,fanout:广播 特点 广播所有消息:将消息…...
作为点的对象CenterNet论文阅读
摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表,并对每一个位置进行分类。这种做法既浪费又低效,并且需要额外的后处理。在本文中,我们采取了不同的方法。我们将物体建模为单…...
持续交付的进化:从DevOps到AI驱动的IT新动能
文章目录 一、持续交付的本质:从手动到自动的交付飞跃关键特性案例:电商平台的高效部署 二、持续交付的演进:从CI到AI驱动的未来发展历程 中国…...
生成对抗网络(GAN)损失函数解读
GAN损失函数的形式: 以下是对每个部分的解读: 1. , :这个部分表示生成器(Generator)G的目标是最小化损失函数。 :判别器(Discriminator)D的目标是最大化损失函数。 GAN的训…...
结合PDE反应扩散方程与物理信息神经网络(PINN)进行稀疏数据预测的技术方案
以下是一个结合PDE反应扩散方程与物理信息神经网络(PINN)进行稀疏数据预测的技术方案,包含完整数学推导、PyTorch/TensorFlow双框架实现代码及对比实验分析。 基于PINN的反应扩散方程稀疏数据预测与大规模数据泛化能力研究 1. 问题定义与数学模型 1.1 反应扩散方程 考虑标…...
智能照明系统:具备认知能力的“光神经网络”
智能照明系统是物联网技术与传统照明深度融合的产物,其本质是通过感知环境、解析需求、自主决策的闭环控制,重构光与人、空间、环境的关系。这一系统由智能光源、多维传感器、边缘计算单元及云端管理平台构成,形成具备认知能力的“光神经网络…...
