LeetCode 437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

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

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

前缀和 + 回溯

前缀和：从根到当前节点的路径上，所有节点的元素的和（包含当前元素）。

若处于同一路径上的节点 A 和 B ，若 “节点 B 的前缀和 - 节点 A 的前缀和 = target”，则说明节点 A 和 B 之间的元素之和为 target ，即节点 A 和 B 之间的这段路径为满足题目要求的路径。

可利用回溯遍历整棵树，并用上述方法统计出满足要求的路径数量。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {     
        // 保存路径中的前缀和，key是前缀和, value是大小为key的前缀和出现的次数
        Map<Integer, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0, 1);     // 处理某条路径的 currsum 恰好等于 targetSum 的情况
        return recur(root, prefixSumMap, targetSum, 0);  
    }

    private int recur(TreeNode root, Map<Integer, Integer> prefixSumMap, int targetSum, int currSum) {
        if (root == null) return 0;
        int res = 0;
        currSum += root.val;    // 从根到当前节点的前缀和

        // 若Map中前缀和为currSum - targetSum的出现次数大于0，说明中间存在和为targetSum的路径
        res += prefixSumMap.getOrDefault(currSum - targetSum, 0);
        
        // 保存当前路径的前缀和
        prefixSumMap.put(currSum, prefixSumMap.getOrDefault(currSum, 0) + 1);

        res += recur(root.left, prefixSumMap, targetSum, currSum);
        res += recur(root.right, prefixSumMap, targetSum, currSum);
        
        // 向上回溯，删除当前路径，恢复状态
        prefixSumMap.put(currSum, prefixSumMap.get(currSum) - 1);
        return res;
    }
}

• 时间复杂度：O(n) ，树的每个节点遍历一次
• 空间复杂度：O(n)