【第十周】路径总和 III

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)
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容