路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

img

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

因为不需要从根节点开始，所以需要对每一个节点进行求最大路径操作。

使用深搜，递归函数返回值是以该节点为根的树的路径总和为target的个数。

返回条件是如果遍历到空节点，返回0。

否则：递归调用左子树和右子树

返回左子树个数+右子树个数

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

class Solution {
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int res = dfs(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    private int dfs(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        if (root.val == targetSum) {
            res++;
        }
        res += dfs(root.left, targetSum - root.val);
        res += dfs(root.right, targetSum - root.val);
        return res;
    }
}

使用前缀和进行优化，某个节点前缀和表示从根节点到该节点途径所有点的路径之和，使用哈希表存储该条链路的前缀和和对应的出现次数。

当前节点的前缀和表示为cur，如果该条链路中存在一个长度为target的路径，那么cur-target应该存在哈希表中，也就是res+=map.getOrDefault(cur-target,0)

递归函数返回时应该把当前节点的<前缀和,出现次数> 清空，一直递归到根节点后该条链的哈希表就会清空，然后就会继续操作另一条链

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

class Solution {
    Map<Long, Integer> map = new HashMap<>();
    long target;

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        map.put(0L, 1);
        return dfs(root, 0L);
    }

    private int dfs(TreeNode root, long sum) {
        if (root == null) {
            return 0;
        }
        sum += root.val;
        int res = map.getOrDefault(sum - target, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        int left = dfs(root.left, sum);
        int right = dfs(root.right, sum);
        res = res + left + right;
        map.put(sum, map.get(sum) - 1);
        return res;

    }
}