LeetCode_ Binary tree_ Prefix and_ Medium_ 437. path sum III

1. subject

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 The number of paths for .

The path doesn't need to start at the root , 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
explain ： And equal to 8 There are 3 strip , As shown in the figure .

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

Tips ：
The range of the number of nodes in a binary tree is [0,1000]
-109 <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/path-sum-iii

2. Ideas

（1） The prefix and
Questions about prefixes and , May refer to LeetCode_ The prefix and _ secondary _560. And for K Subarray This question . This topic needs to apply the knowledge of prefix and to the binary tree .

3. Code implementation （Java）

// Ideas 1———— The prefix and 
/** * 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 {
    
    /*  Record prefix and   Start with the root node of the binary tree , Lu jinhewei  pathSum  There are  preSumCnt.get(pathSum)  strip  */
    HashMap<Integer, Integer> preSumCnt = new HashMap<>();
    int pathSum, targetSum;
    int res = 0;

    public int pathSum(TreeNode root, int targetSum) {
    
        if (root == null) {
    
            return 0;
        }
        this.pathSum = 0;
        this.targetSum = targetSum;
        this.preSumCnt.put(0, 1);
        traverse(root);
        return res;
    }

    public void traverse(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        // Preorder traversal position 
        pathSum += root.val;
        /*  Start with the root node of the binary tree , Path and are  pathSum - targetSum  The number of paths   Is the path and for  targetSum  The number of paths  */
        res += preSumCnt.getOrDefault(pathSum - targetSum, 0);
        // The record starts from the root node of the binary tree , Path and are  pathSum  The number of paths 
        preSumCnt.put(pathSum, preSumCnt.getOrDefault(pathSum, 0) + 1);
        traverse(root.left);
        traverse(root.right);
        // Postorder traversal position 
        preSumCnt.put(pathSum, preSumCnt.get(pathSum) - 1);
        pathSum -= root.val;
    }
}