力扣437. 路径总和 III

Problem: 437. 路径总和 III

文章目录

  • 题目描述
  • 思路
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

1.定义int类型函数rootSum(root, targetSum),用于求取每一个节点等于目标函数的路径数:

1.1.易知rootSum(root, targetSum)求出的数量等于rootSum(root.left, targetSum - value)求出的数量加上rootSum(root.right, targetSum - value)求出的数量,其中value是当前遍历到的节点的节点值
1.2.若当前的value值等于targetSum,则所求的路径总和加一;

2.在pathSum函数中实现对每一个节点调用rootSum函数得出最终的路劲总和数

复杂度

时间复杂度:

O ( n 2 ) O(n^2) O(n2);其中 n n n为二叉树节点的个数

空间复杂度:

O ( n ) O(n) O(n)

Code

/*** 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 {/*** Path Sum III** @param root      The root of binary tree* @param targetSum The target number* @return int*/public int pathSum(TreeNode root, long targetSum) {if (root == null) {return 0;}int res = rootSum(root, targetSum);res += pathSum(root.left, targetSum);res += pathSum(root.right, targetSum);return res;}/*** Find the sum of the target paths of each node** @param root      The root of binary tree* @param targetSum The target number* @return int*/public int rootSum(TreeNode root, long targetSum) {int res = 0;if (root == null) {return 0;}int value = root.val;if (value == targetSum) {res++;}res += rootSum(root.left, targetSum - value);res += rootSum(root.right, targetSum - value);return res;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/321560.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

excel如何将多列数据转换为一列?

这个数据整理借用数据透视表也可以做到: 1.先将数据源的表头补齐,“姓名” 2.点击插入选项卡,数据透视表,在弹出对话框中,数据透视位置选择 现有工作表,(实际使用时新建也没有问题)…

机器学习项目实践-基础知识部分

环境建立 我们做项目第一步就是单独创建一个python环境,Python新的隔离环境 创建:python -m venv ml 使用:.\Scripts\activate python -m venv ml 是在创建一个名为 ml 的虚拟环境,这样系统会自动创建一个文件夹ml,…

crossover怎么打开软件 mac怎么下载steam crossover下载的软件怎么运行

CrossOver是一款Mac和Linux平台上的类虚拟机软件,通过CrossOver可以运行Windows的可执行文件。如果你是Mac用户且需要使用CrossOver,但是不知道CrossOver怎么打开软件,如果你想在Mac电脑上玩Windows游戏,但不知道怎么下载Steam&am…

Springboot 集成 Consul 实现服务注册中心-05

因为后续很多模块都要用到注册中心,所以此处先实现此模块。 Consul简介 Consul是一个开源的服务发现和配置管理工具,具有跨平台、运行高效等特点。它由HashiCorp公司开发,并使用Go语言编写。Consul主要用于实现分布式系统中的服务发现、健康…

把项目打包成Maven Archetype(多模块项目脚手架)

1、示例项目 2、在pom.xml中添加archetype插件 <plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-archetype-plugin</artifactId><version>3.2.0</version> </plugin>3、打包排除某些目录 当我们使用…

扭蛋机小程序在互联网浪潮中的崛起与发展

随着互联网的快速发展&#xff0c;各种线上娱乐方式层出不穷&#xff0c;其中扭蛋机小程序凭借其独特的魅力&#xff0c;在互联网浪潮中迅速崛起并发展壮大。扭蛋机小程序不仅打破了传统扭蛋机的地域限制和操作不便&#xff0c;还融入了丰富的互动元素和便捷性&#xff0c;满足…

Jmeter页面汉化和字体显示过小调整

在频繁解压使用Jmeter的时候&#xff0c;经常会遇到需要将页面的英文调整为中文&#xff0c;页面文字和编辑区域内容文字显示较小的问题&#xff0c;记录一下方便以后查阅。 1.页面汉化 Jmeter在解压启动之后页面显示是英文&#xff0c;如果需要修改为中文&#xff0c;可以修改…

做题速度太慢了,面不上

没办法&#xff0c;之前练了一个月的sql。两个月不写&#xff0c;现在差不多忘干净了。工作空窗期&#xff0c;或者休息期不能太久&#xff0c;不然学再多的内容都可能会忘完的。 sql题&#xff0c;腾讯四道sql题&#xff0c;限时45分钟完成。我只做了一道&#xff0c;还没做完…

java接受入参是xml格式参数demo

java接受入参是xml格式参数demo 依赖demo1. xml入参定义2.接口定义3. postman请求4. 结果 注解说明 依赖 pom依赖 jackson-dataformat-xml <dependency><groupId>com.fasterxml.jackson.dataformat</groupId><artifactId>jackson-dataformat-xml</…

基于web的物流管理系统

文章目录 项目介绍主要功能截图&#xff1a;部分代码展示设计总结项目获取方式 &#x1f345; 作者主页&#xff1a;超级无敌暴龙战士塔塔开 &#x1f345; 简介&#xff1a;Java领域优质创作者&#x1f3c6;、 简历模板、学习资料、面试题库【关注我&#xff0c;都给你】 &…

顺序表的实现(迈入数据结构的大门)

什么是数据结构 数据结构是由&#xff1a;“数据”与“结构”两部分组成 数据与结构 数据&#xff1a;如我们所看见的广告、图片、视频等&#xff0c;常见的数值&#xff0c;教务系统里的&#xff08;姓名、性别、学号、学历等等&#xff09;&#xff1b; 结构&#xff1a;当…

项目经理【人】任务

系列文章目录 【引论一】项目管理的意义 【引论二】项目管理的逻辑 【环境】概述 【环境】原则 【环境】任务 【环境】绩效 【人】概述 【人】原则 【人】任务 一、定义团队的基本规则&塔克曼阶梯理论 1.1 定义团队的基本规则 1.2 塔克曼阶梯理论 二、项目经理管理风格 …

uts插件开发-继uniapp原生插件nativeplugins,uts插件开发可直接操作原生安卓sdk等,支持uniappx,支持源码授权价格等等

1.创建uts项目 2.创建uts插件cf-takepic 3.在index.uts中编写原生安卓代码&#xff0c;首先定义一个函数方法&#xff0c;在页面中看是否可引用成功 uts函数代码 /*** 拍照函数*/ export const takepicfunction():void{console.log("11111111") } index.vue代码 …

简单两步将Lllama、Qwen等开源大模型安装到自己的电脑上

现在已经有非常多优秀的开源大语言模型了&#xff0c;比如Command R、Mistral、Qwen、MiniMax、Baichuan、Phi3等&#xff0c;其中Lllama3和Qwen等已经和GPT4的性能比较接近了。 如果能把这些免费的开源大模型部署到本地电脑或手机上&#xff0c;可以完全自由的使用&#xff0…

Misc 流量分析

流量分析简介 网络流量分析是指捕捉网络中流动的数据包&#xff0c;并通过查看包内部数据以及进行相关的协议、流量分析、统计等来发现网络运行过程中出现的问题。 在CTF比赛中&#xff0c;以及各种技能大赛对于流量包的分析取证是一种十分重要的题型。通常这类题目都是会提供…

DirClass

DirClass 通过分析&#xff0c;发现当接收到DirClass远控指令后&#xff0c;样本将返回指定目录的目录信息&#xff0c;返回数据中的远控指令为0x2。 相关代码截图如下&#xff1a; DelDir 通过分析&#xff0c;发现当接收到DelDir远控指令后&#xff0c;样本将删除指定目录…

xv6源码分析 017

xv6源码分析 017 在buffer cache上面的就是logging层了&#xff0c;这一层主要的工作是维持每一个文件系统写入的操作的原子性。什么是原子性&#xff1f;通俗地来讲&#xff0c;原子性可以这样理解&#xff0c;如果一组操作&#xff08;或者一个操作&#xff09;在执行的时候…

神经网络极简入门

神经网络是深度学习的基础&#xff0c;正是深度学习的兴起&#xff0c;让停滞不前的人工智能再一次的取得飞速的发展。 其实神经网络的理论由来已久&#xff0c;灵感来自仿生智能计算&#xff0c;只是以前限于硬件的计算能力&#xff0c;没有突出的表现&#xff0c;直至谷歌的A…

AI数据中心网络技术选型,InfiniBand与RoCE对比分析

InfiniBand与RoCE对比分析&#xff1a;AI数据中心网络选择指南 随着 AI 技术的蓬勃发展&#xff0c;其对数据中心网络的要求也日益严苛。低延迟、高吞吐量的网络对于处理复杂的数据密集型工作负载至关重要。本文分析了 InfiniBand 和 RoCE 两种数据中心网络技术&#xff0c;帮助…

MySQL数据库练习——视图

schooldb库——utf8字符集——utf8_general_ci排序规则 先创建库&#xff0c;再去使用下列的DDL语句。 DDL CREATE TABLE student (id int(11) NOT NULL AUTO_INCREMENT COMMENT 学号,createDate datetime DEFAULT NULL COMMENT 创建时间,modifyDate datetime DEFAULT NULL …