2022-02-18(437. 路径总和 III)

2024-04-07 23:38
文章标签 路径 02 18 iii 2022 总和 437

本文主要是介绍2022-02-18(437. 路径总和 III),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

方法1:遍历

/*** 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 {public int pathSum(TreeNode root, int targetSum) {if(root==null){return 0;}return thisNodeSum(root,targetSum)+pathSum(root.left,targetSum)+pathSum(root.right,targetSum);}public int thisNodeSum(TreeNode root,int targetSum){if(root==null){return 0;}int a=targetSum-root.val;int count=0;if(a==0){++count;}count+=(thisNodeSum(root.left,targetSum-root.val)+thisNodeSum(root.right,targetSum-root.val));return count;}
}

方法2:前缀和(空间换时间)

主要学习的题解:https://leetcode-cn.com/problems/path-sum-iii/solution/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/

1 前缀和:一个节点的前缀和就是该节点到根之间的路径和
2 HashMap的key是前缀和, value是该前缀和的节点数量,记录数量是因为有出现复数路径的可能
3 本质还是空间换时间,保存各种前缀和出现的次数。
即:要寻找的前缀和=根节点到当前节点的路径和-targetSum

/*** 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 {int wholeTargetSum;Map<Integer,Integer> map;public int pathSum(TreeNode root, int targetSum) {wholeTargetSum=targetSum;map=new HashMap<>();map.put(0,1);    //十分重要的一行,不然就不能从根节点开始算了return dfs(root,0);}public int dfs(TreeNode root,int pre){if(root==null){return 0;}int pathSum=pre+root.val;   //获取节点到当前节点root的路径和pathSumint needPrefix=pathSum-wholeTargetSum;  //得到需要的前缀和needPrefixint count=map.getOrDefault(needPrefix,0);   //得到needPrefix对应次数/*添加该前缀和到map中,给子节点使用这行代码不能放在 int count=map.getOrDefault(needPrefix,0); 之前,因为路径不能不包括任何节点*/map.put(pathSum,map.getOrDefault(pathSum,0)+1);    count+=dfs(root.left,pathSum);count+=dfs(root.right,pathSum);map.put(pathSum,map.get(pathSum)-1);  //去除这个前缀和对应的次数return count;}
}// class Solution {
//     Map<Integer, Integer> prefixMap;
//     int target;//     public int pathSum(TreeNode root, int sum) {
//         prefixMap = new HashMap<>();
//         target = sum;//         prefixMap.put(0, 1);
//         return recur(root, 0);
//     }//     private int recur(TreeNode node, int curSum) {
//         if(node == null) {
//             return 0;
//         }//         int res = 0;
//         curSum += node.val;//         res += prefixMap.getOrDefault(curSum - target, 0);
//         prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) + 1);//         int left = recur(node.left, curSum);
//         int right = recur(node.right, curSum);//         res = res + left + right;//         prefixMap.put(curSum, prefixMap.get(curSum) - 1);//         return res;
//     }
// }

这篇关于2022-02-18(437. 路径总和 III)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

Git 的特点—— Git 学习笔记 02

文章目录 Git 简史Git 的特点直接记录快照,而非差异比较近乎所有操作都是本地执行保证完整性一般只添加数据 参考资料 Git 简史 众所周知,Linux 内核开源项目有着为数众多的参与者。这么多人在世界各地为 Linux 编写代码,那Linux 的代码是如何管理的呢?事实是在 2002 年以前,世界各地的开发者把源代码通过 diff 的方式发给 Linus,然后由 Linus

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

vcpkg子包路径批量获取

获取vcpkg 子包的路径,并拼接为set(CMAKE_PREFIX_PATH “拼接路径” ) import osdef find_directories_with_subdirs(root_dir):# 构建根目录下的 "packages" 文件夹路径root_packages_dir = os.path.join(root_dir, "packages")# 如果 "packages"

MySQL record 02 part

查看已建数据库的基本信息: show CREATE DATABASE mydb; 注意,是DATABASE 不是 DATABASEs, 命令成功执行后,回显的信息有: CREATE DATABASE mydb /*!40100 DEFAULT CHARACTER SET utf8mb3 / /!80016 DEFAULT ENCRYPTION=‘N’ / CREATE DATABASE myd

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 (1)任务并行 (2)数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间,需要在两者之间相互传输数据。 (1)分配GPU内存 (2)将CPU上的数据复制到GPU上 (3)在GPU上对数据进行计算操作 (4)将计算结果从GPU复制到CPU上 (5)释放GPU内存 CUDA内存管理API (1)分配内存 cudaErro

react笔记 8-18 事件 方法 定义方法 获取/改变数据 传值

1、定义方法并绑定 class News extends React.Component {constructor(props) {super(props)this.state = {msg:'home组件'}}run(){alert("我是一个run") //方法写在类中}render() {return (<div><h2>{this.state.msg}</h2><button onCli