leetcode 437. Path Sum III | 437. 路径总和 III（DFS，前缀和）

阳光穿透心脏的1/2处 2022-09-04 04:56 148阅读 0赞

## 题目 ##

[https://leetcode.com/problems/path-sum-iii/][https_leetcode.com_problems_path-sum-iii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

DFS+前缀和问题，注意节点可能为 0 的情况（也是因此发现应该用 HashMap 记录前缀和的个数而不是用 HashSet 仅记录前缀和的数值）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
    class Solution { 
        public int pathSum(TreeNode root, int targetSum) { 
            int count = 0;
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
            return dfs(root, 0, targetSum, map, count);
        }
    
        public int dfs(TreeNode node, int sum, int target, Map<Integer, Integer> map, int count) { 
            if (node == null) return count;
            sum += node.val;
    
            if (map.containsKey(sum - target)) { 
                count += map.get(sum - target);
            }
            if (!map.containsKey(sum)) { 
                map.put(sum, 0);
            }
    
            map.put(sum, map.get(sum) + 1);
            count = dfs(node.left, sum, target, map, count);
            count = dfs(node.right, sum, target, map, count);
            map.put(sum, map.get(sum) - 1);
    
            return count;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_path-sum-iii]: https://leetcode.com/problems/path-sum-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/7362787d14d6460497116d8a9ed26db9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/c66e73a5c60e4f7599f840307eb57739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/136ab8306d5e42a1807f6ccbc309409a.png