LeetCode437：路径总和III

要求

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

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

思路

前缀和：该节点到根之间的路径和，也就是说到达当前元素的路径上，之前所有元素的和。
节点8的前缀和：1 + 2 + 4 + 8 = 15
节点9的前缀和：1 + 2 + 5 + 9 = 17

  	 1
 	/  \
   2    3
  / \    \
 4   5    6
/ \   \
7  8   9
1
2
3
4
5
6
7

题目要求的是找出路径和等于给定数值的路径总数, 而：两节点间的路径和 = 两节点的前缀和之差

                 1
                / 
               2    
              / 
             3   
            / 
           4
1
2
3
4
5
6
7

假如题目给定数值为5

节点1的前缀和为: 1
节点3的前缀和为: 1 + 2 + 3 = 6
prefix(3) - prefix(1) == 5
所以 节点1 到 节点3 之间有一条符合要求的路径( 2 --> 3 )

---

---

HashMap存的是什么？
HashMap的key是前缀和， value是该前缀和的节点数量，记录数量是因为有出现复数路径的可能。

恢复状态的意义
由于题目要求：路径方向必须是向下的（只能从父节点到子节点）
当我们把一个节点的前缀和信息更新到map里时，它应当只对其子节点们有效。
状态恢复代码的作用就是： 在遍历完一个节点的所有子节点后，将其从map中除去。

public class LeetCode437 {
    public int pathSum(TreeNode root, int targetSum) {
        //key是前缀和，value是大小为key的前缀和出现的次数
        Map<Long, Integer> prefixSumCount = new HashMap<>();
        //前缀和为0的一条路径
        prefixSumCount.put(0L,1);
        //前缀和的递归回溯思路
        return recursionPathSum(root,prefixSumCount,targetSum,0L);
    }

    /**
     * 从当前节点反推到根节点(反推比较好理解，正向其实也只有一条)，有且仅有一条路径，因为这是一棵树
     * 如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
     * 所以前缀和对于当前路径来说是唯一的，当前记录的前缀和，在回溯结束，回到本层时去除，保证其不影响其他分支的结果
     * @param node 树节点
     * @param prefixSumCount 前缀和Map
     * @param target 目标值
     * @param currSum 当前路径和
     * @return 满足题意的解
     */
    private int recursionPathSum(TreeNode node, Map<Long, Integer> prefixSumCount, int target, long currSum) {
        //递归终止条件
        if (node == null) {
            return 0;
        }

        int res = 0;
        //当前路径和，当前层
        currSum += node.val;
        // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径
        // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
        // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
        res += prefixSumCount.getOrDefault(currSum-target,0);
        //更新路径上当前节点前缀的个数
        prefixSumCount.put(currSum,prefixSumCount.getOrDefault(currSum,0)+1);

        //进入下一层
        res += recursionPathSum(node.left,prefixSumCount,target,currSum);
        res += recursionPathSum(node.right,prefixSumCount,target,currSum);

        //回到本层，回复状态，去除当前节点的前缀和数量
        prefixSumCount.put(currSum,prefixSumCount.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45