題目

https://leetcode.com/problems/path-sum-iii/

題解

DFS+前綴和問題，注意節點可能為 0 的情況（也是因此發現應該用 HashMap 記錄前綴和的個數而不是用 HashSet 僅記錄前綴和的數值）。

/*** 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;} }

總結

以上是生活随笔為你收集整理的leetcode 437. Path Sum III | 437. 路径总和 III（DFS，前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。