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

LeetCode算法题(Go语言实现)_36

news 来源：原创 2025/9/20 17:58:00

题目

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

一、代码实现（双重递归法）

func pathSum(root *TreeNode, targetSum int) int {if root == nil {return 0}// 计算以当前节点为起点的路径数 + 左右子树的路径数return dfs(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}func dfs(node *TreeNode, remain int) int {if node == nil {return 0}count := 0if node.Val == remain {count++}// 递归处理左右子树，更新剩余目标值count += dfs(node.Left, remain - node.Val)count += dfs(node.Right, remain - node.Val)return count
}

二、算法分析（递归法）

1. 核心思路

双重递归结构：外层递归遍历所有节点作为路径起点，内层递归计算以该节点为起点的路径数目
暴力穷举：对每个节点及其子树进行深度优先搜索，统计符合条件的路径

2. 关键步骤

外层递归：遍历每个节点作为可能的路径起点
内层递归：以当前节点为起点，向下搜索满足sum=targetSum的路径
终止条件：空节点返回0，当前节点值等于剩余值时计数+1
状态传递：将剩余值remain - node.Val传递给子树

3. 复杂度

指标	值	说明
时间复杂度	O(n²)	每个节点触发一次O(n)的子树遍历
空间复杂度	O(h)	h为树高度（递归栈空间）

三、代码实现（前缀和优化法）

func pathSum(root *TreeNode, targetSum int) int {prefixSum := make(map[int]int)prefixSum[0] = 1 // 处理根节点自身满足条件的情况return dfs(root, 0, targetSum, prefixSum)
}func dfs(node *TreeNode, currSum int, target int, prefixSum map[int]int) int {if node == nil {return 0}currSum += node.Valcount := prefixSum[currSum - target]prefixSum[currSum]++count += dfs(node.Left, currSum, target, prefixSum)count += dfs(node.Right, currSum, target, prefixSum)prefixSum[currSum]-- // 回溯return count
}

四、算法分析（前缀和法）

1. 核心思路

前缀和哈希表：记录从根节点到当前节点的路径和出现次数
数学关系：若存在currSum - target = oldSum，则oldSum -> currSum的路径和为target

2. 关键步骤

初始化哈希表：预存prefixSum[0]=1处理根节点自身满足条件的情况
更新当前和：累加节点值到currSum
查询差值：计算currSum - target的出现次数
回溯操作：维护哈希表状态避免子树间的干扰

3. 复杂度

指标	值	说明
时间复杂度	O(n)	单次遍历所有节点
空间复杂度	O(n)	哈希表存储n个节点的前缀和

五、图解示例

以root = [10,5,-3,3,2,null,11], targetSum=8为例：

        10/  \5   -3/ \    \3   2   11

前缀和法流程：

路径10→5→3：和为18 → 18-8=10（无记录）
路径10→5→2：和为17 → 17-8=9（无记录）
路径10→5：和为15 → 15-8=7（无记录）
路径10→-3→11：和为18 → 18-8=10（命中初始0）
最终计数：3（路径5→3、路径5→2→1、路径-3→11）

六、边界条件与扩展

1. 特殊场景验证

空树：返回0
负数和零：如root = [-2,null,-3], target=-5 → 返回1
重复路径：多节点值相同的情况需正确计数

2. 扩展应用

多条件路径统计：同时满足和值与节点数限制
动态目标值：支持实时修改targetSum的在线查询
路径回溯：记录具体路径而非仅计数（需维护路径栈）

七、总结与优化方向

1. 方法对比

方法	优势	劣势	适用场景
双重递归	实现简单	时间复杂度高	小规模树(n<1000)
前缀和	线性时间复杂度	需要维护哈希表状态	大规模树

2. 工程优化

并行计算：对左右子树进行并发遍历（Go协程）
内存预分配：根据树高度预判哈希表容量
数值溢出处理：使用int64存储累加和

3. 算法扩展

K路径问题：统计和值为targetSum的TopK最长路径
三维路径：推广到三叉树等复杂结构
流式处理：支持无法完整加载内存的超大树结构

LeetCode算法题(Go语言实现)_36

题目给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点…...

编程日记 2025/9/20 17:58:00

牛客华为机试--HJ48 从单向链表中删除指定值的节点C++

题目描述示例1 示例2 该题的核心是每来一组数据，都要从头开始找，找到数据后再插入。而不是直接在尾部插入数据。上代码 #include <iostream> using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nu…...

编程日记 2025/9/16 4:21:29

Jmeter 插件【性能测试监控搭建】

1. 安装Plugins Manager 1.1 下载路径： Install :: JMeter-Plugins.org 1.2 放在lib/ext目录下 1.3 重启Jmeter，会在菜单-选项下多一个 Plugins Manager菜单，打开即可对插件进行安装、升级。 2. 客户端(Jmeter端) 2.1 安装plugins manager…...

编程日记 2025/9/18 12:28:31

从攻防演练到AI防护：网络安全服务厂商F5的全方位安全策略

随着AI和云原生技术的蓬勃兴起，多云架构的广泛采用，企业内部IT系统正经历着翻天覆地的变化。在这个转型期，传统的攻击手段和防守策略正面临着巨大的挑战。基于此，用户需要跳出传统的思维模式，采取新的视角，…...

编程日记 2025/9/18 5:35:24

【Introduction to Reinforcement Learning】翻译解读5

4 核心算法我们将算法分为三类：基于价值的方法、基于策略的方法和混合算法。 4.1 基于价值的方法Value-based 一个重要的突破是Q-learning的引入，它是一种无模型算法，被视为off-policy时间差分（TD）学习。TD学习无疑…...

编程日记 2025/9/13 1:01:23

Jmeter中的bzm-concurrency thread group 与普通线程组的区别

在 JMeter 中，bzm - Concurrency Thread Group（由 BlazeMeter 提供）和标准的 Thread Group 是两种不同的线程组实现，主要区别在于并发控制模型和负载调节方式。以下是详细对比： 1. 核心区别特性bzm - Concurrency Thread Group标准 Thread Group负载模型基于并发数（C…...

编程日记 2025/9/20 4:49:14

如果你需要将Word文档的内容导入Excel工作表来进行数据加工，使用下面的代码可以实现： Sub ImportWordToExcel()Dim wordApp As Word.ApplicationDim wordDoc As Word.DocumentDim excelSheet As WorksheetDim filePath As VariantDim i As LongDim para…...

编程日记 2025/9/12 6:54:54

ubuntu22部署 3d-tiles-tools

安装fnm curl -fsSL https://fnm.vercel.app/install | bash安装nodejs 20.17.0LTS版本 https://nodejs.org/zh-cn/download/package-manager安装依赖包 # Download and install nvm: curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.40.2/install.sh | bash# in…...

编程日记 2025/9/13 6:30:34

WebStrom关闭模板字符串自动转换

WebStrom关闭模板字符串自动转换 Editor > General > smart Keys > JavaScript > Automatically replace string literal with template string on typing "${"...

编程日记 2025/8/26 22:21:29

【零基础入门unity游戏开发——动画篇】新动画Animator的使用 —— AnimatorController和Animator的使用

考虑到每个人基础可能不一样，且并不是所有人都有同时做2D、3D开发的需求，所以我把【零基础入门unity游戏开发】分为成了C#篇、unity通用篇、unity3D篇、unity2D篇。【C#篇】：主要讲解C#的基础语法，包括变量、数据类型、运算符、…...

编程日记 2025/9/18 14:11:49

npx vite 可以成功运行，但 npm run dev 仍然报错 Missing script: “dev“

npx vite 可以成功运行，但 npm run dev 仍然报错 Missing script: "dev"，说明问题可能出在 npm 的脚本解析或项目配置上。以下是具体解决方案： 1. 检查 package.json 的物理位置可能原因：你当前运行的目录下可能有一个无效的 package.json，而真正的 packa…...

编程日记 2025/9/8 0:18:43

Java 泛型的逆变与协变：深入理解类型安全与灵活性

泛型是 Java 中强大的特性之一，它提供了类型安全的集合操作。然而，泛型的类型关系（如逆变与协变）常常让人感到困惑。本文将深入探讨 Java 泛型中的逆变与协变，帮助你更好地理解其原理和应用场景。一、什么是协变与…...

编程日记 2025/9/20 2:14:14

C语言核心知识点整理：结构体对齐、预处理、文件操作与Makefile

目录结构体的字节对齐预处理指令详解文件操作基础Makefile自动化构建总结 1. 结构体的字节对齐字节对齐原理内存对齐：CPU访问内存时，对齐的地址能提高效率。操作系统要求变量按类型大小对齐。对齐规则： 每个成员的起始地址必须是min(成…...

编程日记 2025/9/16 4:57:38

深度学习|注意力机制

一、注意力提示随意：跟随主观意识，也就是指有意识。注意力机制：考虑“随意线索”，有一个注意力池化层，将会最终选择考虑到“随意线索”的那个值二、注意力汇聚这一部分也就是讲第一大点中“注意力汇聚”那个池化…...

编程日记 2025/9/16 6:00:25

特权FPGA之乘法器

完整代码如下： timescale 1ns / 1ps// Company: // Engineer: // // Create Date: 23:08:36 04/21/08 // Design Name: // Module Name: mux_16bit // Project Name: // Target Device: // Tool versions: // Description: // // Dependencies: …...

编程日记 2025/9/18 15:48:58

安全的企业局域网聊天工具哪个好用？

在当今数字化时代，企业对于局域网聊天工具的需求日益增长，尤其是在对数据安全和定制化服务有较高要求的大中型政企单位中。安全的企业局域网聊天工具哪个好用？虽然市面上有很多即时通讯软件，今天来介绍一下已经拥有十年行业经验的…...

编程日记 2025/9/12 5:33:23

如何应对客户频繁变更需求

如何应对客户频繁变更需求？要点包括： 快速响应、深入沟通、灵活规划、过程记录、风险管控。这些策略既能降低项目失控风险，也能帮助团队在变动环境中保持高效率。其中深入沟通尤为关键，它不仅能够让团队第一时间了解客户意图&…...

编程日记 2025/9/10 10:41:15

R语言进行聚类分析

目录简述6种系统聚类法实验实例和数据资料： 上机实验步骤： 进行最短距离聚类： 进行最长距离聚类： 进行中间距离聚类： 进行类平均法聚类： 进行重心法聚类： 进行ward.D聚类：…...

编程日记 2025/9/17 21:08:56

1.6-抓包技术（Burp Suite\Yakit抓包\Web、APP、小程序）

1.6-抓包技术（Burp Suite\Yakit抓包\Web、APP、小程序） 如果要使用抓包软件，基本上第一步都是要安装证书的。原因如下： 客户端（浏览器或应用）会检测到证书不受信任，并弹出证书错误&#xff0…...

编程日记 2025/9/16 7:48:37

DAPP实战篇：使用web3.js连接合约

说明本系列内容目录：专栏：区块链入门到放弃查看目录如果你还没有创建好项目请先查看：《DApp实战篇：先用前端起个项目》，如果你还不知道web3.js是什么请先查看：《DApp实战篇：前端技术栈一览》。安装点此查看web3.js官方文档打开项目根目录，并唤起终端：键入w…...

编程日记 2025/9/11 18:35:52

用 Python 构建一个简单的本地视频流媒体服务器

你是否曾经想过在本地网络上轻松地将电脑上的视频分享给手机或平板电脑观看？也许你下载了一部电影，想在客厅的智能电视上播放，却不想费力地拷贝文件。今天，我们将深入分析一个 Python 脚本，它使用 wxPython 创建图形用…...

编程日记 2025/9/9 15:53:41

汇丰xxx

1. Spring Boot 的了解，解决什么问题？ 我的理解： Spring Boot 是一个基于 Spring 框架的快速开发脚手架，它简化了 Spring 应用的初始搭建和开发过程。解决的问题： 简化配置： 传统的 Spring 应用需要大量的…...

编程日记 2025/9/10 18:33:30

ruby基础语法

以下是 Ruby 基础语法的简明总结，适合快速入门： 一、变量与常量局部变量小写字母或下划线开头，作用域为当前代码块。 name "Alice" _age 20实例变量以开头，属于对象实例。 name "Bob"类变量以开头…...

编程日记 2025/9/7 13:29:46

智体OS-V3.1版：新增了rt-datalink底层数据链通讯，实现【无网络】本机使用

##智体OS-V3.1版本发布更新简介 dtns.os智体OS-V3.1版：新增了rt-datalink底层数据链通讯（使用本地局域网的websocket端口通讯），解决了本机【无网络】正常使用的问题。更新内容 dtns.connector支持使用新的rt-datalink与智体…...

编程日记 2025/9/18 15:02:18

Windows系统安装Git以及Git常用命令介绍

本文主要介绍Windows系统安装Git的方法，以及Git常用命令介绍。一、下载Git 官网： Git - Downloads (git-scm.com) 根据自己的系统选择我的是64位的Windows系统，选择对应的安装包，点击后开始下载等待下载完成二、安装Git 双…...

编程日记 2025/9/15 21:49:29

HTML 开发者的智能助手：通义灵码在 VSCode 中的应用

引言在 HTML 开发领域，提高编码效率和质量是每位开发者追求的目标。通义灵码，作为一款由阿里云技术团队开发的智能编码助手，能够通过其强大的 AI 能力，为 HTML 开发者提供包括代码自动补全、智能注释、代码优化等多方面的支持。…...

编程日记 2025/9/10 20:52:47

MySQL随机获取记录之方法（The Method of Randomly Obtaining Records in MySQL）

MySQL中如何随机获取一条记录随机获取一条记录是在数据库查询中常见的需求，特别在需要展示随机内容或者随机推荐的场景下。在 MySQL 中，有多种方法可以实现随机获取一条记录，每种方法都有其适用的情况和性能特点。在本文中，我们将…...

编程日记 2025/9/11 21:33:13

ngx_core_module 的 create_conf

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_core_module-CSDN博客定义在 src\core\nginx.c ngx_module_t ngx_core_module {NGX_MODULE_V1,&ngx_core_module_ctx, /* module context */ngx_core_commands, /* module directives */…...

编程日记 2025/9/18 22:44:30

41--华为IPSec主备链路实验：当加密隧道遇上“双保险“

🚦 华为IPSec主备链路实验：当加密隧道遇上"双保险" “如果你的IPSec隧道只有一条路，那就像走钢丝不系安全带——刺激但危险！” —— 本文将用华为设备打造主备双加密通道，结合IP-link智能检测，让…...

编程日记 2025/9/20 4:51:12

Reactive编程框架与工具

文章目录 6.2 后端 Reactive 框架6.2.1 Spring WebFlux核心架构核心组件实际应用高级特性性能优化适用场景与限制 6.2.2 Akka（Actor模型）Actor模型基础基本用法高级特性响应式特性实现性能优化实际应用场景优势与挑战 6.2.3 Vert.x（事件驱动&…...

编程日记 2025/9/9 1:33:53

vi/vim常用快捷键

那么今天我们继续昨天没有介绍完的vi编辑器,来看看常用的一些快捷键,方便我们对文件的编辑. 1.拷贝当前行yy,拷贝当前行向下的5行5yy,并粘贴(输入p) 2.删除当前行dd,删除当前行向下的5行5d 3.在文件中查找某个单词[命令模式/关键字,回车查找,输入n就是查找下一个] ⭐️&…...

编程日记 2025/9/15 18:37:51

初始JavaEE篇 —— SpringBoot 统一功能处理

找往期文章包括但不限于本期文章中不懂的知识点： 个人主页：我要学编程程(ಥ_ಥ)-CSDN博客所属专栏：JavaEE 目录前言拦截器基本使用拦截器的路径配置统一数据返回格式统一异常处理前言在实际开发中，某些功能需要强…...

编程日记 2025/9/20 10:37:11

Spring AI Alibaba 文档检索使用

一、文档检索 (Document Retriever)简介 1、核心概念文档检索（DocumentRetriever）是一种信息检索技术，旨在从大量未结构化或半结构化文档中快速找到与特定查询相关的文档或信息。文档检索通常以在线(online)方式运行。 DocumentRetriever通…...

编程日记 2025/9/18 11:49:59

遍历算法及其应用详解

李升伟整理什么是遍历？ 遍历是指按照某种规则或顺序，系统地访问数据结构（如树、图等）中的每个节点一次且仅一次的过程。遍历是算法设计中的基本操作，用于访问、检查或修改数据结构中的所有元素。主要遍历算法 1…...

编程日记 2025/9/19 8:48:23

.NET-EFCore基础知识

.NET EF Core（Entity Framework Core）是微软开发的一款开源的对象关系映射（ORM）框架，用于在.NET 应用程序中与数据库进行交互。以下是一些.NET EF Core 的基础知识： 1. 什么是 EF Core EF Core 是.NET 平…...

编程日记 2025/9/9 12:28:27

R语言基础包可视化（一：axis函数）

R语言基础包可视化（一：axis函数）背景axis函数（坐标轴函数）各参数的图片示例hadj和padjline和poslty,lwd,lwd.ticksgap.axis总结背景之前在介绍正态Q-Q图的过程中，画过标准正态分布的随机数、分数数、分布函数、密度函数的图像，相关的文章连接参考此处：R语言正态Q-Q图…...

编程日记 2025/9/11 17:42:25

Axure疑难杂症：垂直菜单折叠与展开（玩转垂直菜单）

亲爱的小伙伴，在您浏览之前，烦请关注一下，在此深表感谢！课程主题：垂直菜单折叠与展开主要内容：折叠与展开效果应用场景：PC后台菜单、动态下拉菜单、商品分类选择等折叠与展开场景案例展示：案例视频：垂直菜单折叠与展开效果正文内容：关于垂直菜单的折叠与…...

编程日记 2025/9/18 12:39:36

docker 中跑faster-whisper 教程（1050显卡）

之前我本地机器运行faster-whisper 会报错类似 Could not load library libcudnn_ops_infer.so.8github 上也有类似的情况 ：https://github.com/SYSTRAN/faster-whisper/issues/516#issuecomment-2785038635 缺少.so.8 文件，我通过以下方式，…...

编程日记 2025/9/19 1:49:51

MySQL 在 CentOS 7 环境安装完整步骤

1. 卸载已有环境（MariaDB/旧版MySQL） 1.停止 MariaDB 服务 systemctl stop mariadb.service 2.检查并卸载 MariaDB/MySQL 安装包 rpm -qa | grep mariadb # 检查 MariaDB 相关包 rpm -qa | grep mysql # 检查 MySQL 相关包 sudo yum remo…...

编程日记 2025/9/11 11:18:26

下一代智能爬虫框架：ScrapeGraphAI 详解

更多内容请见：爬虫和逆向教程-专栏介绍和目录文章目录一、ScrapeGraphAI 概述1.1 ScrapeGraphAI介绍1.2 核心特点1.3 工作流程1.4 关键模块1.5 对比传统爬虫框架1.6 安装二、基础操作2.1 自定义解析规则2.2 数据后处理2.3 分布式爬取三、高级功能3.1 多步骤交互采集3.2 动态…...

编程日记 2025/9/15 20:01:46

C++-ffmpeg-2-3-工厂模式封装SDL-9-7

1.接口设计 2.窗口渲染器和材质初始化 3.渲染Draw并测试渲染YUV 4.渲染画面随窗口大小自动缩放并抗锯齿 5.清理接口和接收窗口退出事件 1.接口设计：原则主要的实现步骤： main的流程： 1打开文件 yuv_file.open("400_300_25.yuv&quo…...

编程日记 2025/9/19 8:20:06

下载极客漫画——Beautiful Soup实用案例

文章目录一、背景介绍二、实现思路三、效果图四、构思五、实现细节 1. 第一步下载网页 2. 寻找和下载漫画图像 3. 保存图像，找到前⼀张漫画六、完整代码七、程序输出八、附录九、总结一、背景介绍 XKCD网站是一个关于浪漫、隐喻、数字、以及…...

编程日记 2025/9/10 8:07:16

【大模型理论篇】SWIFT: 可扩展轻量级的大模型微调基础设施

1. 背景大模型(LLM)和多模态大模型(MLLM)利用基于Transformer的架构获得了很迅速的发展。为满足对这些模型的训练和轻量级微调需求，目前已有一些开源框架，如LLaMA-Factory、Firefly、FastChat、Axolotl和LMFlow等。但这些框架在支持的模型、技术和功能上…...

编程日记 2025/9/4 20:47:05

利用 schedule 模块在每日上午每 3 秒执行任务

一、schedule 模块基础原理与功能概述 schedule 模块维护了一个任务队列，每个任务都关联着一个特定的时间触发器和对应的执行函数。当系统时间到达任务设定的触发时间时，模块会从队列中取出相应的任务并执行其关联的函数。这种设计模式使得开发者无需过多关注底层的时间处理…...

编程日记 2025/9/9 17:52:34

ruby超高级语法

以下是 Ruby 中一些极度硬核的语法和底层特性，涉及元编程的深渊、虚拟机原理、语法黑魔法等，适用于追求极限的 Ruby 开发者： 一、语法核弹级操作 1. 动态修改继承链 class A; def foo; "A"; end end class B; def foo; "B…...

编程日记 2025/9/10 19:35:26

Java Stream API：现代化集合处理的艺术

Java Stream API：现代化集合处理的艺术引言在Java 8中引入的Stream API彻底改变了我们处理集合数据的方式。它不仅仅是一个新的工具集，更代表了一种声明式、函数式的编程范式。本文将深入探讨Java Stream的核心概念、使用场景和最佳实践。一、什么是Stream？ Stream（…...

编程日记 2025/9/18 16:49:01