437. Path Sum III

, , ,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        // 从当前节点向下满足路径和的路径数量
        int pathCount = dfs(root, targetSum);

        // 因为题目要求路径不需要从根节点开始，即从任意节点开始均可，所以需要以下两行递归调用，注意对 pathSum 是递归调用
        pathCount += pathSum(root.left, targetSum);
        pathCount += pathSum(root.right, targetSum);

        return pathCount;
    }

    private int dfs(TreeNode node, int targetSum) {
        if (node == null) {
            return 0;
        }

        int pathCount = 0;

        if (node.val == targetSum) {
            pathCount++;
        }

        pathCount += dfs(node.left, targetSum - node.val);
        pathCount += dfs(node.right, targetSum - node.val);

        return pathCount;
    }
}

Backtracking + Prefix Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixSumToCountMap = new HashMap<>();
        prefixSumToCountMap.put(0L, 1);
        return dfs(prefixSumToCountMap, root, 0, targetSum);
    }

    private int dfs(Map<Long, Integer> prefixSumToCountMap, TreeNode node, long prefixSum, int targetSum) {
        if (node == null) {
            return 0;
        }

        prefixSum += node.val;
        int pathCount = prefixSumToCountMap.getOrDefault(prefixSum - targetSum, 0); // 注意此处是 prefixSum - targetSum, 不要搞反了
        prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.getOrDefault(prefixSum, 0) + 1);
        pathCount += dfs(prefixSumToCountMap, node.left, prefixSum, targetSum);
        pathCount += dfs(prefixSumToCountMap, node.right, prefixSum, targetSum);
        prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.get(prefixSum) - 1);
        return pathCount;
    }
}

References

437. Path Sum III
剑指 Offer II 050. 向下的路径节点之和