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

力扣113:路径总和II

给你二叉树的根节点 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
输出:[]

代码:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define Maxsize 1024// returnSize: 一个指针,用于返回满足条件的路径数量(即最终返回的二维数组的行数)
// returnColumnSizes: 一个指针,用于返回一个数组,该数组存储最终返回的二维数组中每条路径的长度(即二维数组中每列的长度)
// result: 二维整数数组指针,用于存储满足条件的路径数组
// temp: 整数数组,用于临时存储从根节点到当前节点遍历过程中的路径上的节点值
// NodeNum: 用于暂存当前路径上的节点数量
void DFS(struct TreeNode* root, int sum, int* returnSize, int** returnColumnSizes, int** result, int* temp, int NodeNum)
{// 如果当前节点的值等于目标和sum,并且当前节点是叶子节点(即没有左子节点且没有右子节点)if (root->val == sum && root->left == NULL && root->right == NULL){// 将当前节点的值添加到临时路径数组temp中,并更新当前路径上的节点数量NodeNumtemp[NodeNum++] = root->val;// 为当前满足条件的路径分配内存空间,大小为当前路径上的节点数量乘以每个节点值占用的空间result[*returnSize] = malloc(NodeNum * sizeof(int));// 将临时路径数组temp中的值复制到刚分配好的内存空间中,形成一条完整的满足条件的路径for (int i = 0; i < NodeNum; i++){result[*returnSize][i] = temp[i];}// 将当前路径的长度(即NodeNum)存储到用于记录每条路径长度的数组returnColumnSizes中,并更新满足条件的路径数量*returnSize(*returnColumnSizes)[(*returnSize)++]= NodeNum;}else{// 将当前节点的值添加到临时路径数组temp中,并更新当前路径上的节点数量NodeNumtemp[NodeNum++]= root->val;// 如果当前节点的左子节点不为空,递归调用DFS函数继续在左子树中寻找满足条件的路径// 此时目标和更新为sum减去当前节点的值,因为已经将当前节点的值加入到了路径中if (root->left!= NULL) DFS(root->left, sum - root->val, returnSize, returnColumnSizes, result, temp, NodeNum);// 如果当前节点的右子节点不为空,递归调用DFS函数继续在右子树中寻找满足条件的路径// 同样,目标和更新为sum减去当前节点的值if (root->right!= NULL) DFS(root->right, sum - root->val, returnSize, returnColumnSizes, result, temp, NodeNum);}
}// returnSize: 一个指针,用于返回满足条件的路径数量(即最终返回的二维数组的行数)
// returnColumnSizes: 一个指针,用于返回一个数组,该数组存储最终返回的二维数组中每条路径的长度(即二维数组中每列的长度)
int** pathSum(struct TreeNode* root, int sum, int* returnSize, int** returnColumnSizes)
{// 如果根节点为空,说明是空树,直接返回NULL,表示没有找到满足条件的路径if (root == NULL) return NULL;// 定义一个整数数组temp,用于临时存储从根节点到当前节点遍历过程中的路径上的节点值,假设最多能容纳Maxsize个节点值int temp[Maxsize];// 初始化返回的二维整数数组,用于存储满足条件的路径数组,假设最多能容纳Maxsize条路径int** result = malloc(Maxsize * sizeof(int*));// 为用于记录每条路径长度的数组分配内存空间,假设最多能容纳Maxsize条路径的长度信息*returnColumnSizes = malloc(Maxsize * sizeof(int));// 初始化满足条件的路径数量为0*returnSize = 0;// 调用DFS函数开始在二叉树中深度优先搜索,寻找满足条件的路径DFS(root, sum, returnSize, returnColumnSizes, result, temp, 0);// 返回存储满足条件的路径的二维数组,调用者可以通过该数组获取所有满足条件的路径及其长度信息return result;
}

相关文章:

力扣113:路径总和II

给你二叉树的根节点 root 和一个整数目标和 targetSum &#xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出&a…...

JavaScript字符串常用方法

在JavaScript中&#xff0c;字符串是用来表示文本数据的基本数据类型。字符串可以用单引号()、双引号(")、或反引号()包裹。JavaScript中的字符串是不可变的&#xff0c;也就是说&#xff0c;字符串的值一旦创建就无法更改&#xff0c;但可以创建新字符串来替换原有字符串…...

xtu oj 加一

样例输入# 2 4 1 2 3 4 4 3 2 4 1样例输出# 3 5 解题思路&#xff1a;最小操作次数一定是把所有数变成数组中最大值max。 1、找最大值&#xff0c;一开始我把max初始值设为0&#xff0c;如果a[i]>max,maxa[i],WA了。又看了一遍题目&#xff0c;发现所有整数的绝对值小于…...

QTcpSocket 服务端和客户端

前提&#xff1a; pro文件中添加 QT network 服务端主要采用信号槽机制&#xff0c;代码如如下 核心代码头文件#ifndef TCPSERVER_H #define TCPSERVER_H#include <QObject>#include <QTcpServer> #include <QTcpSocket> #include <QDebug> #inclu…...

Isaac Sim+SKRL机器人并行强化学习

目录 Isaac Sim介绍 OmniIssacGymEnvs安装 SKRL安装与测试 基于UR5的机械臂Reach强化学习测评 机器人控制 OMNI GYM环境编写 SKRL运行文件 训练结果与速度对比 结果分析 运行体验与建议 Isaac Sim介绍 Isaac Sim是英伟达出的一款机器人仿真平台&#xff0c;适用于做机…...

项目中用户数据获取遇到bug

项目跟练的时候 Uncaught (in promise) TypeError: Cannot read properties of undefined (reading ‘code’) at Proxy.userInfo (user.ts:57:17) 因此我想要用result接受信息的时候会出错&#xff0c;报错显示为result.code没有该值 导致我无法获取到相应的数据 解决如下 给…...

SpringSecurity+jwt+captcha登录认证授权总结

SpringSecurityjwtcaptcha登录认证授权总结 版本信息&#xff1a; springboot 3.2.0、springSecurity 6.2.0、mybatis-plus 3.5.5 认证授权思路和流程&#xff1a; 未携带token&#xff0c;访问登录接口&#xff1a; 1、用户登录携带账号密码 2、请求到达自定义Filter&am…...

项目技术栈-解决方案-web3去中心化

web3去中心化 Web3 DApp区块链:钱包:智能合约:UI:ETH系开发技能树DeFi应用 去中心化金融P2P 去中心化网络参考Web3 DApp 区块链: 以以太坊(Ethereum)为主流,也包括Solana、Aptos等其他非EVM链。 区块链本身是软件,需要运行在一系列节点上,这些节点组成P2P网络或者半…...

【AI声音克隆整合包及教程】第二代GPT-SoVITS V2:创新与应用

一、引言 随着科技的迅猛发展&#xff0c;声音克隆技术已经成为一个炙手可热的研究领域。SoVITS&#xff08;Sound Voice Intelligent Transfer System&#xff09;&#xff0c;作为该领域的先锋&#xff0c;凭借其卓越的性能和广泛的适用性&#xff0c;正在为多个行业带来前所…...

分清数据链路层、网络层、传输层的区别,以及这些层面的代表协议

目录 数据链路层 网络层 传输层 数据链路层 OSI模型的第二层&#xff0c;负责在相邻节点之间传输帧&#xff0c;处理帧的封装、地址、差错控制和流量控制等。确保数据在物理介质上可靠地传输&#xff0c;并为上层协议提供服务。 以太网&#xff08;Ethernet&#xff09;&…...

git没有识别出大写字母改成小写重命名的文件目录

Git 默认不会跟踪大写字母和小写字母的区别&#xff0c;因为在大多数文件系统中&#xff0c;大写字母和小写字母被认为是相同的文件&#xff0c;只有在区分大小写的文件系统中&#xff08;如 macOS 的 HFS 或 Windows 的 NTFS&#xff09;&#xff0c;这才是一个问题。 如果重命…...

自己动手写Qt Creator插件

文章目录 前言一、环境准备1.先看自己的Qt Creator IDE的版本2.下载源码 二、使用步骤1.参考原本的插件2.编写自定义插件1.cmakelist增加一个模块2.同理&#xff0c;qbs文件也增加一个3.插件源码 三、效果总结 前言 就目前而言&#xff0c;Qt Creator这个IDE&#xff0c;插件比…...

数据重塑:长宽数据转换【基于tidyr】

在数据分析和可视化过程中&#xff0c;数据的组织形式直接影响着我们能够进行的分析类型和可视化效果。这里简单介绍两种常见的数据格式&#xff1a;长格式&#xff08;Long Format&#xff09;和宽格式&#xff08;Wide Format&#xff09;&#xff0c;以及如何使用tidyr包进行…...

多模态大模型开启AI社交新纪元,Soul App创始人张璐团队亮相2024 GITEX GLOBAL

随着AI在全球范围内的加速发展和广泛应用,各行业纷纷在此领域发力。作为全球最大的科技盛会之一,2024年的GITEX GLOBAL将目光再次聚焦于人工智能的飞速发展,吸引了超过6700家来自各个领域的企业参与。在这样的背景下,Soul App作为国内较早将AI技术应用于社交领域的平台,首次亮相…...

实验6记录网络与故障排除

实验6记录网络与故障排除 实验目的及要求&#xff1a; 通过实验&#xff0c;掌握如何利用文档记录网络设备相关信息并完成网络拓扑结构的绘制。能够使用各种技术和工具来找出连通性问题&#xff0c;使用文档来指导故障排除工作&#xff0c;确定具体的网络问题&#xff0c;实施…...

QEMU 模拟器中运行的 Linux 系统

这两个文件通常用于在 QEMU 模拟器中运行的 Linux 系统&#xff0c;具体作用如下&#xff1a; 1. linux-aarch64-qemu.ext4&#xff1a; - **文件类型**&#xff1a;这是一个文件系统镜像文件&#xff0c;通常是 ext4 文件系统格式。 - **作用**&#xff1a;它包含了 Li…...

Ceph PG(归置组)的状态说明

Ceph PG&#xff08;Placement Group&#xff09;的状态反映了Ceph集群中数据的健康状况和分布情况。以下是Ceph PG的一些常见状态&#xff1a; Creating&#xff1a;创建状态。在创建存储池时&#xff0c;会创建指定数量的归置组&#xff08;PG&#xff09;。Ceph在创建一或多…...

Docker使用docker-compose一键部署nacos、Mysql、redis

下面是一个简单的例子&#xff0c;展示如何通过Docker Compose文件部署Nacos、MySQL和Redis。请确保您的机器上已经安装了Docker和Docker Compose。 1&#xff0c;准备好mysql、redis、nacos镜像 sudo docker pull mysql:8 && sudo docker pull redis:7.2 &&…...

HTTP常见的状态码有哪些,都代表什么意思

HTTP 协议定义了一系列的状态码&#xff0c;用于描述服务器对客户端请求的处理结果。这些状态码分为五个类别&#xff0c;每个类别都有特定的用途。 常见状态码 1开头 信息性状态码 这些状态码表示请求已被接收&#xff0c;继续处理。 100 Continue&#xff1a;客户端应继续…...

WebKit的Windows接口(适用2024年11月份版)

WebKit的Windows接口 使用cairo作为图形后端&#xff0c;libcurl作为网络后端。并且它只支持64位的Windows。 安装开发工具 安装带有“使用c进行桌面开发”工作负载的最新Visual Studio。 Activate Developer Mode.激活开发者模式。Build-webkit脚本创建一个指向生成的comp…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...