Leetcode skimming diary sword finger offer II 050. sum of downward path nodes

Original link （https://leetcode.cn/problems/6eUYwP/)

Title Description

Given the root node of a binary tree root , And an integer targetSum , Find that the sum of the node values in the binary tree is equal to targetSum Of route Number of .
route You don't need to start at the root node , It doesn't need to end at the leaf node , But the path has to be down （ Only from parent node to child node ）.

Example 1

Input ：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output ：3

Example 2

Input ：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output ：3

Data constraints

• The range of the number of nodes in a binary tree is [0,1000]
• -10^9 <=Node.val <= 10^9
• -1000 <= targetSum <= 1000

Ideas

The sum of the data values corresponding to the calculation path must be the preorder traversal of the binary tree, and the value can be calculated in the preorder traversal , But the title representation does not necessarily start from the root node , So other nodes that are not leaf nodes also need to be counted , If you simply use each node as the root node to traverse , There must be a lot of double counting , In response to this double counting, we can consider using a hash table to record the previously calculated values , So there is a value equal to the current value minus targetSum Then it proves that there is a way to get what is targetSum, For this kind of data storage, you can use Map Come and save , It can store both numerical values and quantities .

Code

/** * 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 pathCount(TreeNode root, int targetSum, long pre, Map<Long, Integer> map) {
    
		if (root == null) {
    
			return 0;
		}
		pre += root.val;
		int  ans = map.getOrDefault(pre - targetSum, 0);
		map.put(pre, map.getOrDefault(pre, 0) + 1);
		ans += pathCount(root.left, targetSum, pre, map);
		ans += pathCount(root.right, targetSum, pre, map);
		map.put(pre, map.getOrDefault(pre, 0) - 1);
		return ans;
	}

	public int pathSum(TreeNode root, int targetSum) {
    
		Map<Long, Integer> map = new HashMap<>();
		map.put(0l, 1);
		return pathCount(root, targetSum, 0L, map);

	}
}