Skip to main content

🟡 剑指 Offer II 050. 向下的路径节点之和

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解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 {    private int cnt = 0;    private int target = 0;    private Map<Integer, Integer> sumset;
    private void dfs(TreeNode node, int curSum) {        curSum += node.val;        cnt += sumset.getOrDefault((curSum - target), 0);        sumset.put(curSum, sumset.getOrDefault(curSum, 0)+1);
        if (node.left != null) {            dfs(node.left, curSum);        }                if (node.right != null) {            dfs(node.right, curSum);        }
        sumset.put(curSum, sumset.get(curSum)-1);    }
    public int pathSum(TreeNode root, int targetSum) {        sumset = new HashMap<>();        target = targetSum;        sumset.put(0, 1);
        if (root == null) {            return 0;        }        dfs(root, 0);
        return cnt;    }}