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

(树) 剑指 Offer 34. 二叉树中和为某一值的路径 ——【Leetcode每日一题】

❓ 剑指 Offer 34. 二叉树中和为某一值的路径

难度:中等

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 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:

在这里插入图片描述

输入:root = [1,2,3], targetSum = 5
输出:[]

示例 3:

输入:root = [1,2], targetSum = 0
输出:[]

提示

  • 树中节点总数在范围 [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

注意:本题与 113. 路径总和 II 相同。

💡思路:dfs

深度优先搜索的方式,枚举每一条从根节点到叶子节点的路径。

  • 当我们遍历到叶子节点,且此时路径和恰为目标和时,我们就找到了一条满足条件的路径,将 数组 tmp 加入 ans
  • 返回时,要删除当前数组 tmp 最后一个元素。

🍁代码:(C++、Java)

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 {
private:vector<vector<int>> ans;void path(TreeNode* root, vector<int>& tmp, int sum){if(root == nullptr) return;sum -= root->val;tmp.push_back(root->val);if(sum == 0 && root->left == nullptr && root->right == nullptr) {ans.push_back(tmp);}else{path(root->left, tmp, sum);path(root->right, tmp, sum);}tmp.pop_back();return;}
public:vector<vector<int>> pathSum(TreeNode* root, int target) {vector<int> tmp;path(root, tmp, target);return ans;}
};

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 {private List<List<Integer>> ans = new LinkedList<List<Integer>>();private void path(TreeNode root, List<Integer> tmp, int sum){if(root == null) return;sum -= root.val;tmp.add(root.val);if(sum == 0 && root.left == null && root.right == null) {ans.add(new LinkedList(tmp));}else{path(root.left, tmp, sum);path(root.right, tmp, sum);}tmp.remove(tmp.size() - 1);return;}public List<List<Integer>> pathSum(TreeNode root, int target) {List<Integer> tmp = new LinkedList<>();path(root, tmp, target);return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n 为树的节点数。在最坏情况下,树的上半部分为链状,下半部分为完全二叉树,并且从根节点到每一个叶子节点的路径都符合题目要求。此时,路径的数目为 O ( n ) O(n) O(n),并且每一条路径的节点个数也为 O ( n ) O(n) O(n),因此要将这些路径全部添加进答案中,时间复杂度为 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度 O ( n ) O(n) O(n),空间复杂度主要取决于栈空间的开销,栈中的元素个数不会超过树的节点数。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

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

相关文章:

(树) 剑指 Offer 34. 二叉树中和为某一值的路径 ——【Leetcode每日一题】

❓ 剑指 Offer 34. 二叉树中和为某一值的路径 难度&#xff1a;中等 给你二叉树的根节点 root 和一个整数目标和 targetSum &#xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a…...

HDFS集群滚动升级以及回滚相关

HDFS集群滚动升级以及回滚相关 介绍不停机滚动升级非联邦HA集群联邦HA集群 停机升级--非HA集群HDFS集群降级和回滚异同点共同点不同点 HA集群降级&#xff08;downgrade&#xff09;注意事项 集群回滚操作 介绍 在hadoop v2中&#xff0c;HDFS支持namenode高可用&#xff08;H…...

【LeetCode】094. 分割回文串II

文章目录 1. 解题思路1.1 创建dp表1.2 状态转移方程1.3 提前求出所有子串是否是回文串 2. 整体代码 1. 解题思路 1.1 创建dp表 这道题我们使用动态规划的方法来解&#xff0c;首先创建一个大小为字符串长度的dp表。dp[i] 表示 s[0, i] 的字符串最小划分多少次可以全划分为回文…...

CBCGPRibbon 添加背景图片

resource.h中声明资源的ID&#xff1a;ID_RIBBON_BACKIMAGE rc文件中添加png图片路径&#xff1a; ID_RIBBON_BACKIMAGE PNG DISCARDABLE "res\\bkribbon.png" 代码中添加下测&#xff1a; //添加背景图片 m_wndRibbonBar.SetBackgroundImage(ID_RIB…...

无涯教程-Perl - last 语句函数

当在循环内遇到 last 语句时&#xff0c;循环立即终止&#xff0c;程序控制在循环后的下一条语句处恢复。您可以为LABEL提供最后一个语句&#xff0c;其中LABEL是循环的标签。 last 语句可以在嵌套循环内使用&#xff0c;如果未指定LABEL&#xff0c;则该语句将适用于最近的循环…...

网络安全 Day13-Linux三剑客awk知识

Linux三剑客awk知识 1. awk 介绍2. awk 语法3. 练习 1. awk 介绍 awk 是一门语言, 也是一个命令,Linux 有三剑客命令: grep/sed/awk三剑客的特长 grep 过滤内容sed 取行awk 取列 2. awk 语法 取列 取第一列文件($1): awk {print $1} 文件指定分隔符为文件: awk -F "指…...

java讲解Spring Boot配置文件级别 相互覆盖关系 解决一方不愿意给数据库密码 一方不愿意给源码时 数据库配置问题

前面 我们讲过Spring Boot 修改临时变量的方式 但另一个场景 就是 我们 在本地开发环境 用的是一个配置 但如果项目经理上线 他想改这些配置 怎么弄呢 特别是数据库之类的配置 很多线上是不太一样的 那么 我们先看一个比较基本的方法 在配置文件的同目录下创建一个目录 叫 con…...

点击表格行高亮

css中三元表达式 :class"[activeIndex index ? color : , item]"点击行高亮 <div click"actvied(index)" :class"[activeIndex index ? color : , item]"v-for"(item, index) in tableData" :key"index">{{ item…...

基于粒子群优化算法的配电网光伏储能双层优化配置模型[IEEE33节点](选址定容)(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f308;4 Matlab代码、数据、讲解 &#x1f4a5;1 概述 由于能源的日益匮乏&#xff0c;电力需求的不断增长等&#xff0c;配电网中分布式能源渗透率不断提高&#xff0c;且逐渐向主动配电网方…...

零代码爬虫平台SpiderFlow的安装

什么是 Spider Flow &#xff1f; Spider Flow 是一个高度灵活可配置的爬虫平台&#xff0c;用户无需编写代码&#xff0c;以流程图的方式&#xff0c;即可实现爬虫。该工具支持多数据源、自动保存至数据库、任务监控、抓取 JS 动态渲染页面、插件扩展&#xff08;OCR 识别、邮…...

Java 与其他编程语言:比较分析

Java 擅长可移植性和可靠性&#xff0c;Python 擅长通用性和简单性&#xff0c;JavaScript 擅长 Web 开发&#xff0c;C 擅长性能&#xff0c;Go 擅长效率。 在广阔的软件开发世界中&#xff0c;选择正确的编程语言对于任何项目的成功都至关重要。Java 是一种以其多功能性和可移…...

Linux性能分析工具介绍(二)--内存、进程、磁盘、IO分析

目录 一、引言 二、Linux性能分析工具介绍 ------>2.1、进程 ------>2.2、内存 ------>2.3、磁盘 ------>2.4、IO 一、引言 本章从内存、IO、进程的角度,分析linux系统的性能 二、Linux性能分析工具介绍 2.1、进程 2.1.1、top top命令可以动态查看进程…...

海外热门地区/国家常见主体证件示例

海外热门地区/国家常见主体证件示例&#xff08;本页面内容较多&#xff0c;你可以通过CtrlF搜索&#xff09; Overseas Popular Areas / Countries Examples of Common certificates &#xff08;This page has more content, you can search by CtrlF&#xff09; 中国香港…...

【阵列信号处理】空间匹配滤波器、锥形/非锥形最佳波束成形器、样本矩阵反演 (SMI) 研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

使用MPU6050计算方向盘角度

我给你们作了榜样、叫你们照着我向你们所作的去作。 ——【约翰福音13:15】 1.前言 前段时间接到一个项目需求&#xff1a;使用现有的陀螺仪MPU6050实现计算当前车辆的方向盘角度。 2.需求分析 MPU6050可获取三轴角速度和三轴加速度&#xff0c;并通过算法可以获得横滚角、…...

区块链实验室(13) - 在PBFT中节点的度与其流量的特征

前面若干实验说明了PBFT的耗时、流量与度的特征&#xff0c;见 区块链实验室(10) - 实例说明PBFT的共识过程, 区块链实验室(11) - PBFT耗时与流量特征, 区块链实验室(12) - 网络拓扑对PBFT共识流量的影响 同样的实验方案&#xff0c;在100个节点构成的无标度网络中完成100次交…...

C++——文件操作

一、文本文件 C中输入输出是通过流对象进行操作&#xff0c;对于文件来说写文件就是将内容从程序输出到文件&#xff0c;需要用到写文件流ofstream&#xff1b;而读文件就是将内容从文件输入到程序&#xff0c;需要用到读文件流ifstream&#xff1b;这两个文件流类都包含在头文…...

channel通道笔记

channel通道笔记 介绍 语法 1.一般使用make创建channel(常用) c : make(chan datatype),datatype是数据类型 2.直接显示声明,创建的值为空,一般没有太大意义 var c chan datatype 三种定义写法: 既可以收数据又可以发数据:chan datatype只可以收数据:chan <- datatype只可…...

无涯教程-Lua - 面向对象

面向对象编程(OOP)是现代编程时代中使用最广泛的编程技术之一。 OOP的特征 类(Class) - 类是用于创建对象的可扩展模板。 对象(Objects) - 它是类的实例&#xff0c;并为其分配了单独的内存空间。 继承(Inheritance) - 这是一个概…...

Java中的IOUtils是什么?

Java中的IOUtils是一个工具类&#xff0c;用于简化文件和流的操作。它提供了一些常用的方法&#xff0c;如复制文件、读取文件、写入文件等。 下面是一个简单的示例&#xff0c;演示如何使用IOUtils来复制文件&#xff1a; import org.apache.commons.io.FileUtils; import j…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...