力扣 | 437. 路径总和 III

437. 路径总和 III

mport java.util.ArrayList;
import java.util.List;/*** int的取值范围：* -2^31 ~ 2^31-1* <p>* -2147483648 ~ 2147483647（约等于10的9次方）* <p>* long long的取值范围：* -2^63 ~ (2^63-1）* <p>* -9223372036854775808 ~ 9223372036854775807（约等于10的18次方）*/
public class Problem_437_PathSum {public int pathSum(TreeNode root, int target) {return dfs(root, new ArrayList<>(), target);}public int dfs(TreeNode node, List<Long> parentPathSumList, int targetSum) {if (node == null) return 0;int cnt = 0;List<Long> tmp = new ArrayList<>();for (int i = 0; i < parentPathSumList.size(); i++) {long sum = parentPathSumList.get(i) + node.val;tmp.add(sum);if (sum == targetSum) cnt++;}tmp.add((long) node.val);if (node.val == targetSum) cnt++;int leftCnt = dfs(node.left, tmp, targetSum);int rightCnt = dfs(node.right, tmp, targetSum);return cnt + leftCnt + rightCnt;}}