LeetCode_二叉树_前缀和_中等_437.路径总和 III

Bertha 。 2023-10-06 22:47 8阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个二叉树的根节点 root ，和一个整数 targetSum ，**求该二叉树里节点值之和等于 targetSum 的路径的数目。**

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

**示例 1：**  
![在这里插入图片描述][53812bee938c4a8a89756103eff664a1.png]  
输入：root = \[10,5,-3,3,2,null,11,3,-2,null,1\], targetSum = 8  
输出：3  
解释：和等于 8 的路径有 3 条，如图所示。

**示例 2：**  
输入：root = \[5,4,8,11,null,13,4,7,2,null,null,5,1\], targetSum = 22  
输出：3

**提示：**  
二叉树的节点个数的范围是 \[0,1000\]  
\-109 <= Node.val <= 109  
\-1000 <= targetSum <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/path-sum-iii

## 2.思路 ##

（1）前缀和  
有关前缀和的题目，可参考[LeetCode\_前缀和\_中等\_560.和为 K 的子数组][LeetCode_560._ K]这题。本题需要将前缀和的知识运用到二叉树中。

相关题目：  
[LeetCode\_二叉树\_简单\_112.路径总和][LeetCode_112.]  
[LeetCode\_二叉树\_中等\_113.路径总和 II][LeetCode_113._ II]  
[LeetCode\_二叉树\_困难\_124. 二叉树中的最大路径和][LeetCode_124.]  
[LeetCode\_前缀和\_哈希表\_中等\_560.和为 K 的子数组][LeetCode_560._ K]

## 3.代码实现（Java） ##

//思路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 {
        
    
        Map<Long, Integer> prefix;
    
        public int pathSum(TreeNode root, int targetSum) {
        
            /*
                定义节点的前缀和为：由根节点到当前节点的路径上所有节点的和
                prefix 中的 key 为节点的前缀和，value 为此前缀和的数量
                例如 <4, 2> 说明根节点到其子节点的路径和为 4 的路径有 2 条
            */
            prefix = new HashMap<>();
            /*
                任何节点本身也可以形成一个路径(长度为 1 的路径)，如果某个节点的值就为 target，
                那么它本身就是一个解，前缀和 0 正好可以与它形成这个解
            */
            prefix.put(0L, 1);
            return traverse(root, 0, targetSum);
        }
    
        public int traverse(TreeNode root, long pathSum, int targetSum) {
        
            if (root == null) {
        
                return 0;
            }
            int res = 0;
            pathSum += root.val;
            res += prefix.getOrDefault(pathSum - targetSum, 0);
            prefix.put(pathSum, prefix.getOrDefault(pathSum, 0) + 1);
            res += traverse(root.left, pathSum, targetSum);
            res += traverse(root.right, pathSum, targetSum);
            prefix.put(pathSum, prefix.getOrDefault(pathSum, 0) - 1);
            return res;
        }
    }

[53812bee938c4a8a89756103eff664a1.png]: https://img-blog.csdnimg.cn/53812bee938c4a8a89756103eff664a1.png
[LeetCode_560._ K]: https://blog.csdn.net/weixin_43004044/article/details/122873498
[LeetCode_112.]: https://blog.csdn.net/weixin_43004044/article/details/130635531
[LeetCode_113._ II]: https://blog.csdn.net/weixin_43004044/article/details/130635921
[LeetCode_124.]: https://blog.csdn.net/weixin_43004044/article/details/124796351