美文网首页
437. path sum III

437. path sum III

作者: 7ccc099f4608 | 来源:发表于2023-01-27 16:20 被阅读0次

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

image.png

前缀和

/**
     *
     * pathSum iii:只要路径向下即可,不要求起终点为root和leaf:返回看加起来 == sum的路径的个数
     *
     * 前缀和
     */
    public int pathSumIII(TreeNode root, int target) {
        if(root == null) {
            return 0;
        }

        Map<Integer, Integer> prefix = new HashMap<>();
        prefix.put(0, 1);

        return helper(root, target, prefix, 0);
    }

    private int helper(TreeNode root, int target, Map<Integer, Integer> prefix, int curSum) {
        if(root == null) {
            return 0;
        }

        int res = 0;
        curSum += root.val;

        // 此前存在路径的个数(A点 和 当前点 的差值是target,那么 A-当前点是有效路径)
        res += prefix.getOrDefault(curSum-target, 0);

        // 回溯
        prefix.put(curSum, prefix.getOrDefault(curSum, 0) + 1);
        res += helper(root.left, target, prefix, curSum);
        res += helper(root.right, target, prefix, curSum);
        prefix.put(curSum, prefix.getOrDefault(curSum, 0) - 1);

        return res;
    }

相关文章

网友评论

      本文标题:437. path sum III

      本文链接:https://www.haomeiwen.com/subject/uxuehdtx.html