路径总和 III

题目链接

路径总和 III

题目描述

注意点

• 二叉树的节点个数的范围是 [0,1000]
• 求该二叉树里节点值之和等于 targetSum 的 路径 的数目

解答思路

• 可根据前缀和的思路解决本题，前缀和表示从根节点开始，往左或往右组成的路径和，统计从根节点开始的所有的前缀和以及前缀和出现的次数，当遍历到任意一个节点时，可根据加上该节点值形成的当前值与目标值的差值（也就是currSum - targetSum）在前缀和中出现的次数推出加上该节点时路径和为targetSum的路径数
• 因为路径方向必须是向下的（只能从父节点到子节点），所以父节点的前缀和只会影响其对应的左右子树，所以在前缀和映射中加上当前节点后递归其左右子树进行相同的操作，且在递归完左右子树后，需要将前缀和映射恢复，防止左右两个子树互相造成影响

代码

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // key为前缀和的值，value为前缀和为key时的路径数量
        Map<Long, Integer> map = new HashMap<>();
        // 没有任何节点时前缀和为0，保证根节点为targetSum也能正确统计路径数
        map.put(0L, 1);
        return recursionPathSum(root, map, 0L, targetSum);
    }

    public int recursionPathSum(TreeNode root, Map<Long, Integer> map, Long currSum, int targetSum) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        currSum += root.val;
        // 根据前一层的前缀和的值推出加上此节点时结果为targetSum的路径数
        res += map.getOrDefault(currSum - targetSum, 0);
        // 增加新的前缀和映射进入下一层对左右子树进行递归
        map.put(currSum, map.getOrDefault(currSum, 0) + 1);
        res += recursionPathSum(root.left, map, currSum, targetSum);
        res += recursionPathSum(root.right, map, currSum, targetSum);
        // 恢复状态，防止左右子树的前缀和各自产生影响
        map.put(currSum, map.get(currSum) - 1);
        return res;
    }
}
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

关键点

• 前缀和的思想
• 父节点的前缀和映射只会对其下方的子树判断路径总和有影响，而不会对同层或更高层的节点产生影响，所以在对子树递归后，还要将该节点的前缀和映射进行恢复