【Hot100】LeetCode—437. 路径总和 III

目录

  • 1- 思路
    • 前缀和+哈希表+dfs
  • 2- 实现
    • ⭐437. 路径总和 III——题解思路
  • 3- ACM 实现


  • 题目连接:437. 路径总和 III

1- 思路

前缀和+哈希表+dfs

① 前缀和

  • 求二叉树的前缀和,每求一次用一个 sum 传参记录更新

② 哈希表

  • key 为前缀和 ,value 为出现频率
  • 用来记录前缀和出现的次数,原理就是如果 sum - targetSum 在前缀和的哈希中,则证明有目标和为 targetSum 的路径。出现次数就是该哈希出现的次数

③ dfs递归三部

  • 3.1 参数返回值,返回 void,参数为 sumroot
  • 3.2 终止条件,遇到 null 直接返回
  • 3.3 递归处理:递归求前缀和,如果哈希表存在sum - targetSum且出现次数大于等于 1 ,收集 res
    • 更新 sum
    • 递归 左节点
    • 递归 右结点
    • 回溯 更新 sum

2- 实现

⭐437. 路径总和 III——题解思路

在这里插入图片描述

class Solution {int targetSum;int res = 0;HashMap<Long,Integer> hash = new HashMap<>();public int pathSum(TreeNode root, int targetSum) {this.targetSum = targetSum;hash.put(0L,1);dfs(0L,root);return res;}public void dfs(Long sum,TreeNode root){// 终止if(root==null){return;}// 递归sum+=root.val;if(hash.containsKey(sum-targetSum) && hash.get(sum-targetSum)>=1){res += hash.get(sum-targetSum);}hash.put((Long)sum,hash.getOrDefault(sum,0)+1);dfs(sum,root.left);dfs(sum,root.right);hash.put((Long)sum,hash.get(sum)-1);}
}

3- ACM 实现

package Daily_LC.Month8_Week4.Day138;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;/*** pathSum** @author alcohol* @Description* @since 2024-08-24 13:40*/
public class pathSum {public static 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;}}public static TreeNode build(String str) {if (str == null || str.length() == 0) {return null;}String input = str.replace("[", "");input = input.replace("]", "");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for (int i = 0; i < parts.length; i++) {if (!parts[i].equals("null")) {nums[i] = Integer.parseInt(parts[i]);} else {nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while (!queue.isEmpty() && index < parts.length) {TreeNode node = queue.poll();if (index < nums.length && nums[index] != null) {node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if (index < nums.length && nums[index] != null) {node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}static int res = 0;static HashMap<Long, Integer> hash = new HashMap<>();public static int pathSum(TreeNode root, int targetSum) {hash.put(0L, 1);dfs(0L, root, targetSum);return res;}public static void dfs(Long sum, TreeNode root, int targetSum) {// 终止if (root == null) {return;}// 递归sum += root.val;if (hash.containsKey(sum - targetSum) && hash.get(sum - targetSum) >= 1) {res += hash.get(sum - targetSum);}hash.put((Long) sum, hash.getOrDefault(sum, 0) + 1);dfs(sum, root.left, targetSum);dfs(sum, root.right, targetSum);hash.put((Long) sum, hash.get(sum) - 1);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);System.out.println("输入目标和");int targetSum = sc.nextInt();pathSum(root, targetSum);System.out.println("结果是" + res);}}

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

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

相关文章

RISCV汇编编程讲解

第一章 引言 为什么要讲riscv&#xff1f; riscv的特点&#xff1a; -诞生于顶尖学术机构&#xff1a;诞生于加州大学伯克利分校的体系结构研究院。吸引了大批的顶尖企业参与&#xff08;e.g. 谷歌、华为、高通、阿里巴巴为rsicv的发展提供了大量的资金支持和贡献了技术和人才…

Oracle Linux 7.9 安装minikube体验

1.环境信息 前置所需&#xff1a; 操作系统&#xff1a;Oracle Linux 7.9 虚拟机配置&#xff1a;CPU:4核 内存&#xff1a;4G 容器&#xff1a;docker 26.1.4 安装minikube后环境&#xff1a; minikube: v1.33.1 kubernetes:v1.23.3 minukube体验说明&#xff1a;使用Virtua…

flume--数据从kafka到hdfs发生错误

解决&#xff1a; #1.将flume自带的依赖删除 mv /opt/installs/flume1.9/lib/guava-11.0.2.jar /opt/installs/flume1.9/lib/guava-11.0.2.jar.bak #2.将hadoop的依赖发送到flume下 cp /opt/installs/hadoop3.1.4/share/hadoop/common/lib/guava-27.0-jre.jar /opt/installs/f…

【C++ Primer Plus习题】5.9

问题: 解答: #include <iostream> #include <cstring> using namespace std;#define SIZE 20int main() {string words[SIZE];string done "done";int count 0;while (true){cout << "请输入单词:" << endl;cin >> words…

中国发布首个AI集成Linux开源操作系统

B站&#xff1a;啥都会一点的研究生公众号&#xff1a;啥都会一点的研究生 AI圈最近又发生了啥新鲜事&#xff1f; 中国大模型市场迎来新格局&#xff1a;百度、商汤、智谱位列前三 国际数据公司&#xff08;IDC&#xff09;于首次发布了《中国大模型平台市场份额&#xff0…

NYX靶机笔记

NYX靶机笔记 概述 VulnHub里的简单靶机 靶机地址&#xff1a;https://download.vulnhub.com/nyx/nyxvm.zip 1、nmap扫描 1&#xff09;主机发现 # -sn 只做ping扫描&#xff0c;不做端口扫描 nmap -sn 192.168.84.1/24 # 发现靶机ip为 MAC Address: 00:50:56:E0:D5:D4 (V…

适用于应用程序安全的 11 大 DevSecOps 工具

DevSecOps&#xff08;开发者安全运营&#xff09;是指将安全最佳实践融入软件开发生命周期的过程&#xff0c;从而实现更好的安全结果。这是提供全面安全基础设施的重要方面。 市场格局&#xff1a;DevSecOps市场竞争激烈。该领域有数百家供应商提供工具&#xff0c;帮助组织…

虚幻5|AI行为树,跟随task(非行为树AI)

这个可以不需要行为树 1.打开ai的角色蓝图后&#xff0c;添加一个函数&#xff0c;命名为跟距离改变速度 并用tick调用 2.编辑函数

在VBA中调用Adobe Acrobat或Reader的命令行工具,实现PDF自动打印 (‾◡◝)

在VBA&#xff08;Visual Basic for Applications&#xff09;中自动打印PDF文件通常不直接支持&#xff0c;因为VBA本身是针对Microsoft Office应用程序&#xff08;如Excel、Word和PowerPoint等&#xff09;的编程语言&#xff0c;并不直接处理PDF文件。但是&#xff0c;你可…

【变化检测】基于Tinycd建筑物(LEVIR-CD)变化检测实战及ONNX推理

主要内容如下&#xff1a; 1、LEVIR-CD数据集介绍及下载 2、运行环境安装 3、Tinycd模型训练与预测 4、Onnx运行及可视化 运行环境&#xff1a;Python3.8&#xff0c;torch1.12.0cu113 likyoo变化检测源码&#xff1a;https://github.com/likyoo/open-cd 使用情况&#xff1a…

学习文件IO,让你从操作系统内核的角度去理解输入和输出(Java实践篇)

本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人…

经验之谈 —— 数据处理与分析的6大Python库

点击下方卡片&#xff0c;关注“小白玩转Python”公众号 Python是一种流行的高级编程语言。它拥有丰富的生态系统和庞大的社区。这个生态系统中有许多优秀的Python库。这些库提供了有用的工具&#xff0c;使开发变得更加容易。本文将介绍6个出色的Python库。这些库在不同领域都…

数据结构初阶(2)——链表OJ

目录 1.面试题 02.02. 返回倒数第 k 个节点 2.OR36 链表的回文结构 3.160. 相交链表 1.面试题 02.02. 返回倒数第 k 个节点 思路&#xff1a;快慢指针&#xff0c;快指针先走k格&#xff0c;慢指针同步 /*** Definition for singly-linked list.* struct ListNode {* i…

android13 隐藏状态栏里面的飞行模式 隐藏蓝牙 隐藏网络

总纲 android13 rom 开发总纲说明 目录 1.前言 2.问题分析 3.代码分析 4.代码修改 5.编译运行 6.彩蛋 1.前言 android13 隐藏状态栏里面的飞行模式,或者其他功能,如网络,蓝牙等等功能,隐藏下图中的一些图标。 2.问题分析 这里如果直接找这个布局的话,需要跟的逻…

[数据集][目标检测]电力场景输电线杆塔塔架金属锈蚀腐蚀生锈检测数据集VOC+YOLO格式1344张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;1344 标注数量(xml文件个数)&#xff1a;1344 标注数量(txt文件个数)&#xff1a;1344 标注…

(南京观海微电子)——直流电源使用介绍

什么是稳压电源&#xff1f;直流稳压电源使用方法教程 在电子技术领域中&#xff0c;稳压电源扮演着举足轻重的角色。那么&#xff0c;究竟什么是稳压电源呢&#xff1f;稳压电源是一种能够提供稳定输出电压的电子装置&#xff0c;其核心功能是在输入电压波动或负载变化的情况…

i.MX6裸机开发(9):CCM时钟控制模块

本章参考资料&#xff1a;《IMX6ULRM》&#xff08;参考手册&#xff09;。 学习本章时&#xff0c;配合《IMX6ULRM》第18章Clock Controller Module (CCM)&#xff0c;效果会更佳&#xff0c;特别是涉及到寄存器说明的部分。 本章我们主要讲解时钟部分&#xff0c;芯片内部的…

摄影曝光:曝光模式认知

写在前面 学习整理《摄影曝光&#xff1a;拍出好照片的49个关键技法》读书笔记博文内容涉及曝光模式简单认知适合小白认知理解不足小伙伴帮忙指正 &#x1f603;,生活加油 99%的焦虑都来自于虚度时间和没有好好做事&#xff0c;所以唯一的解决办法就是行动起来&#xff0c;认真…

【Docker】Docker Consul

docker consul Docker Consul 是一个用于服务发现和配置的开源工具&#xff0c;它是 HashiCorp 公司推出的一个项目。Consul 提供了一个中心化的服务注册和发现系统&#xff0c;可以帮助开发人员轻松地在 Docker 容器和集群之间进行服务发现和配置管理。 Consul 使用基于 HTT…

SQL注入漏洞的基础知识

目录 SQL注入漏洞的定义和原理 SQL注入的类型和攻击方法 SQL注入的防御措施 示例代码 深入研究 SQL注入漏洞的常见攻击场景有哪些&#xff1f; 如何有效防范SQL注入攻击&#xff1f; SQL注入与跨站脚本攻击&#xff08;XSS&#xff09;之间有什么区别&#xff1f; 主要…