力扣热门100题之路径总和III

题目核心一句话求树上有多少条 “向下的路径”和恰好等于 targetSum起点终点任意核心思想超级简单我们要找一段路径和为 target。有一个万能技巧从根走到 A 的和是 sumA从根走到 B 的和是 sumB那么A 到 B 的路径和 sumB - sumA我们想要sumB - sumA target也就是sumA sumB - target只要之前出现过sumB - target这个和就说明存在一条路径满足条件。用走路类比你从根出发往下走每走一步记录当前总路程和前缀和每次都看一眼之前有没有出现过当前和 - target出现过几次就有几条满足条件的路径完整代码实现/** * 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 { private int count 0; public int pathSum(TreeNode root, int targetSum) { // key: 前缀和, value: 出现次数 MapLong, Integer map new HashMap(); map.put(0L, 1); // 初始前缀和0出现1次 dfs(root, 0L, targetSum, map); return count; } public void dfs(TreeNode node, long currSum, int target, MapLong, Integer map) { if (node null) return; // 当前路径和 currSum node.val; // 如果之前出现过 currSum - target说明中间有一段路径和为 target count map.getOrDefault(currSum - target, 0); // 把当前前缀和加入map map.put(currSum, map.getOrDefault(currSum, 0) 1); // 递归左右 dfs(node.left, currSum, target, map); dfs(node.right, currSum, target, map); // 回溯恢复状态 map.put(currSum, map.get(currSum) - 1); } }