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

2024-08-24 15:52

本文主要是介绍【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);}}

这篇关于【Hot100】LeetCode—437. 路径总和 III的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102924

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L