437. Path Sum III

[songyy5517]

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

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

Intuition This problem is to find the number of paths whose sum is equal to targetSum. A simple idea is to travarse every node in the tree, and take each node as the root node to search its paths. However, it requires $O(N^2)$ time. To lower the time complexity, we can utilize the idea of prefix-sum. Specifically, we can record the sum of the paths from the root node to every previous node. When reaching the current node, if there exists a previous prefix sum which is equals to cur_sum - targetSum, then these exists a previous path from whose sum is equals to targetSum.

[songyy5517]

Approach: Prefix Sum & DFS

1. Exception handling;
2. Define a HashMap to store the previous prefix sum and its number, and a global number recording the number of valid paths;
   • Add the initiate state (0, 1) to the hashmap.
3. Travarse every node with DFS; （1）Update the current path sum; （2）Check the hashmap, determine whether there exists a valid path, and update the global path number; （3）Update the number of the current prefix sum in the hashmap; （5）Traverse the left and right node; （6）Back-track: subtract 1 to the number of the current prefix sum in the hashmap;
4. Return the global path number.

Complexity Analysis

• Time complexity: $O(N)$ , looping through the entire tree only once takes $O(N)$ time;
• Space complexity: $O(N)$ , addtionally define a hashmap to store all previous prefix sum of the current path, taking up $O(N)$ space; and in the worst case, the tree would degenerate into a linked list, so the recursion depth would be $N$ , occupying $O(N)$ stack space.

[songyy5517]

/**
 * 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 {
    int num = 0;

    public int pathSum(TreeNode root, int targetSum) {
        // 思路：前缀和 & 哈希表
        // 1. 异常处理
        if (root == null)
            return 0;

        // 2. 定义变量
        HashMap<Long, Integer> prefix_sum = new HashMap();   // 保存前缀和与其相应的路径数
        prefix_sum.put((long)0, 1);

        dfs(root, targetSum, 0, prefix_sum);

        return num;
    }

    void dfs(TreeNode root, int targetSum, long cur_sum, HashMap<Long, Integer> prefix_sum){
        if (root == null)
            return ;

        // 查找是否有合格的路径
        cur_sum += root.val;
        num += prefix_sum.getOrDefault(cur_sum - targetSum, 0);

        // 将当前路径作为前缀和加入哈希表
        prefix_sum.put(cur_sum, prefix_sum.getOrDefault(cur_sum, 0) + 1);

        // dfs
        dfs(root.left, targetSum, cur_sum, prefix_sum);
        dfs(root.right, targetSum, cur_sum, prefix_sum);

        // 回溯
        prefix_sum.put(cur_sum, prefix_sum.get(cur_sum) - 1);
    }
}

[songyy5517]

2024/6/1