048路径总和III

路径总和 III题目链接https://leetcode.cn/problems/path-sum-iii/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答MapLong,Integer map new HashMap();//key:前缀和 value前缀和的个数 public int pathSum(TreeNode root, int targetSum) { map.put(0L,1); return helper(root, 0, targetSum); } public int helper(TreeNode cur, long preSum, int targetSum){ if(cur null){ return 0; } preSum cur.val;//计算到当前节点的前缀和 long target preSum - targetSum; int ans map.getOrDefault(target,0); map.put(preSum, map.getOrDefault(preSum,0) 1); ans ( helper(cur.left, preSum, targetSum) helper(cur.right, preSum, targetSum) ); map.put(preSum, map.getOrDefault(preSum,0) - 1); return ans; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路采用前缀和利用哈希表记录前缀和及其个数。解题思路简单但需注意此题的数值范围较大前缀和用int类型会溢出。看了官方题解后的解答//方法一深度优先搜索 //时间复杂度O(n^2) //空间复杂度O(n) public int pathSum(TreeNode root, long targetSum) { if(root null){ return 0; } int ans curSum(root, targetSum); ans pathSum(root.left, targetSum) pathSum(root.right, targetSum); return ans; } public int curSum(TreeNode cur, long targetSum){ if(cur null){ return 0; } int res curSum(cur.left, targetSum-cur.val) curSum(cur.right, targetSum-cur.val); if(cur.val targetSum){ res; } return res; } //方法二前缀和与我的解答思路一致 //时间复杂度O(n) //空间复杂度O(n) public int pathSum(TreeNode root, int targetSum) { MapLong, Integer prefix new HashMapLong, Integer(); prefix.put(0L, 1); return dfs(root, prefix, 0, targetSum); } public int dfs(TreeNode root, MapLong, Integer prefix, long curr, int targetSum) { if (root null) { return 0; } int ret 0; curr root.val; ret prefix.getOrDefault(curr - targetSum, 0); prefix.put(curr, prefix.getOrDefault(curr, 0) 1); ret dfs(root.left, prefix, curr, targetSum); ret dfs(root.right, prefix, curr, targetSum); prefix.put(curr, prefix.getOrDefault(curr, 0) - 1); return ret; }分析​ 1、方法一的解题思路以每个节点作为起点进行一次深搜来统计答案。​ 2、方法二的解题思路与我的解答一致只是实现上略有差异。总结本题的本质就是两数之和问题只是数值较大需注意数据溢出问题。