路径总和Ⅲ

https://leetcode.cn/problems/path-sum-iii/description/?envTypestudy-plan-v2envIdtop-100-liked题目思路这题是求在二叉树的一条分支上是否有一段子路径它的node值和 等于 targetSum与和为 K 的子数组题 是一样的思路。枚举右端点统计有多少个左端点为了找到有多少个左端点可以使用 MapLong , Integer 存储已经遍历过的左端点和。使用0(1)的时间复杂度就可以找到。为什么哈希表要初始化 map.put(0 ,1) ?答如果 targetSum 1 二叉树的第一个结点的值是 1 如果不把 0 加入到哈希表就找不到这里有一条路径问什么先更新 ans再更新map答如果 targetSum 不等于 0更新先哪一个都一样如果为0 如果先把遍历到当前结点的总和sum加入 map 然后去map中查找sum - targetSum会发现 ans的值多加了一个。递归完左右子树后要恢复现场答比如当前结点是 2 结点我们往 cnt 中记录 2结点的值然后递归 2的左右子树。2的左右子树都是和 结点2 一条路径所以需要 延用 2结点的信息cnt需要记录 2 结点的值。遍历完 1 和 4 之后 return。因为 2 是 1 的左子树遍历完之后需要遍历 1 的右子树因为5 、 6 结点 和 2 结点不在一条路径上所以需要在 cnt 中去除 2结点的信息。代码class Solution { private int ans; private int targetSum; public int pathSum(TreeNode root, int targetSum) { MapLong , Integer map new HashMap(); this.targetSum targetSum; map.put( 0L, 1); dfs(root , 0 , map); return ans; } private void dfs(TreeNode root , long s , MapLong , Integer map){ if(root null) return; s root.val; ans map.getOrDefault(s - targetSum , 0); map.merge(s , 1 ,Integer::sum); dfs(root.left , s , map); dfs(root.right , s , map); map.merge(s , -1 ,Integer::sum); } }