【Hot100】LeetCode—437. 路径总和 III

1- 思路

前缀和+哈希表+dfs

① 前缀和

求二叉树的前缀和，每求一次用一个 sum 传参记录更新

② 哈希表

key 为前缀和，value 为出现频率
用来记录前缀和出现的次数，原理就是如果 sum - targetSum 在前缀和的哈希中，则证明有目标和为 targetSum 的路径。出现次数就是该哈希出现的次数

③ dfs递归三部

3.1 参数返回值，返回 void，参数为 sum 和 root
3.2 终止条件，遇到 null 直接返回
3.3 递归处理：递归求前缀和，如果哈希表存在sum - targetSum且出现次数大于等于 1 ，收集 res
- 更新 sum
- 递归左节点
- 递归右结点
- 回溯更新 sum

2- 实现

⭐437. 路径总和 III——题解思路

在这里插入图片描述

class Solution {int targetSum;int res = 0;HashMap<Long,Integer> hash = new HashMap<>();public int pathSum(TreeNode root, int targetSum) {this.targetSum = targetSum;hash.put(0L,1);dfs(0L,root);return res;}public void dfs(Long sum,TreeNode root){// 终止if(root==null){return;}// 递归sum+=root.val;if(hash.containsKey(sum-targetSum) && hash.get(sum-targetSum)>=1){res += hash.get(sum-targetSum);}hash.put((Long)sum,hash.getOrDefault(sum,0)+1);dfs(sum,root.left);dfs(sum,root.right);hash.put((Long)sum,hash.get(sum)-1);}
}

3- ACM 实现

package Daily_LC.Month8_Week4.Day138;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;/*** pathSum** @author alcohol* @Description* @since 2024-08-24 13:40*/
public class pathSum {public static 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;}}public static TreeNode build(String str) {if (str == null || str.length() == 0) {return null;}String input = str.replace("[", "");input = input.replace("]", "");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for (int i = 0; i < parts.length; i++) {if (!parts[i].equals("null")) {nums[i] = Integer.parseInt(parts[i]);} else {nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while (!queue.isEmpty() && index < parts.length) {TreeNode node = queue.poll();if (index < nums.length && nums[index] != null) {node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if (index < nums.length && nums[index] != null) {node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}static int res = 0;static HashMap<Long, Integer> hash = new HashMap<>();public static int pathSum(TreeNode root, int targetSum) {hash.put(0L, 1);dfs(0L, root, targetSum);return res;}public static void dfs(Long sum, TreeNode root, int targetSum) {// 终止if (root == null) {return;}// 递归sum += root.val;if (hash.containsKey(sum - targetSum) && hash.get(sum - targetSum) >= 1) {res += hash.get(sum - targetSum);}hash.put((Long) sum, hash.getOrDefault(sum, 0) + 1);dfs(sum, root.left, targetSum);dfs(sum, root.right, targetSum);hash.put((Long) sum, hash.get(sum) - 1);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);System.out.println("输入目标和");int targetSum = sc.nextInt();pathSum(root, targetSum);System.out.println("结果是" + res);}}