LeetCode hot100——路径总和 III

题目给定一个二叉树的根节点root和一个整数targetSum求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。示例 1输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8输出3解释和等于 8 的路径有 3 条如图所示。示例 2输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22输出3提示:二叉树的节点个数的范围是[0,1000]-109 Node.val 109-1000 targetSum 1000题解/** * 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 { HashMapLong, Integer map new HashMap(); public int pathSum(TreeNode root, int targetSum) { // 前缀和0出现1次用来处理curSum刚好等于targetSum的情况 map.put(0L, 1); return dfs(root, 0L, targetSum); } int dfs(TreeNode node, long curSum, int targetSum){ if(node null) return 0; curSum node.val; // 看历史是否存在 curSum - targetSum int res map.getOrDefault(curSum - targetSum, 0); // 当前前缀和存入map map.put(curSum, map.getOrDefault(curSum,0)1); // 左右递归 res dfs(node.left, curSum, targetSum); res dfs(node.right, curSum, targetSum); // 回溯退栈的时候撤销别的分支不能看到这个前缀和 map.put(curSum, map.get(curSum)-1); return res; } }