437. 路径总和 III

题解

问题

分析

  1. A和B是一条路径上的节点，root到A的路径和为a，root到B的路径和为b，如果b - a = target，那么A到B就是满足题目要求的一条路径；
  2. 从root到当前节点B路径和为target的数量为B之前有几个路径和为b - target的节点；
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
34
35
36
37
38
39
// 3ms; 38.8MB
class Solution {
    int curSum = 0;

    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return dfs(root, sum, map, 0);
    }

    private int dfs(TreeNode root, int sum, HashMap<Integer, Integer> map, int res) {
        // 递归出口
        if (root == null) {
            return 0;
        }
        // 状态更新
        curSum += root.val;
        int tag = 0;
        if (map.containsKey(curSum - sum)) {
            tag = map.get(curSum - sum);
        }
        if (map.containsKey(curSum)) {
            map.put(curSum, map.get(curSum) + 1);
        } else {
            map.put(curSum, 1);
        }
        // 递归
        res = tag + dfs(root.left, sum, map, res) + dfs(root.right, sum, map, res);
        // 回溯
        if (map.get(curSum) > 0) {
            map.put(curSum, map.get(curSum) - 1);
        } else {
            map.remove(curSum);
        }
        curSum -= root.val;

        return res;
    }
}