LeetCode100之路径总和III(437)--Java

1.问题描述

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例1

输入：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

难度等级

中等

题目链接

路径总和III

2.解题思路

这道题要求节点之和为目标和的所有路径数，说白了，就是将所有节点都当成根节点，把这些节点的所有可能的路径组合都找出来，然后数一下里面有多少节点之和为目标和的路径。

如果把每一个节点都当成根节点找一遍，这道题也是可以通过的，但是效率不高。所以，我们要换另外一种方法，那就是用前缀和的方法。为什么会想到前缀和呢？我们不能发现根节点的所有路径和根节点的子节点的所有路径，它们是有很大的重叠部分的，而如果我们每次都把非重叠的部分存储起来，把重叠部分只进行一次操作，是不是就很像前缀和呢?

我们可以用一个hashMap存储前缀和已经对应出现的次数，并对map进行初始化，前缀和为0出现的次数为1。

        //如果节点为空，直接返回0if(root == null){return 0;}//存储前缀和和对应出现的次数Map<Long,Integer> map = new HashMap<>();//初始化mapmap.put(0L,1);

接着，我们可以利用这个map对树进行前序遍历，我们这里的前序遍历要用到递归的方法，需要传递这么几个参数，要遍历的节点，目标和，当前的总和，以及我们存储前缀和的map。

 public int preOrder(TreeNode root,int targetSum,long curSum,Map<Long,Integer> map).....

首先，我们要确定递归的结束条件，如果节点为空，则返回0。因为节点为空，那肯定不可能等于目标和的。

        //节点为空，直接返回0if(root == null){return 0;}

接着，我们需要定义一个变量来存储符合条件的路径个数。前序遍历的顺序是根左右，所以我们首先要对当前节点进行处理。把当前节点的值累加到当前总和之中，更新当前的总和。

        //更新当前总和curSum += root.val;

然后，我们要从map中查看是否有当前总和减掉目标和之后对应的前缀和，有的话，取出前缀和出现的次数累加到我们的统计变量中。如果不理解这一步，我们可以再次回忆一下我们前缀和代表的含义。我们这里的前缀和代表的是比当前节点高层的那些节点经过的路径的和。

        //存储路径数目int result = map.getOrDefault(curSum - targetSum,0);

接下来，更新当前总和在前缀和map中出现的次数，便于前序遍历子节点时统计符合条件的路径数。再然后，我们就可以递归遍历左右节点，获取以左右节点为根的子树中等于目标和的路径数，并把它们累加到我们的统计变量当中。

        //更新存储前缀和的mapmap.put(curSum,map.getOrDefault(curSum,0)+1);//递归左子树result += preOrder(root.left,targetSum,curSum,map);//递归右子树result += preOrder(root.right,targetSum,curSum,map);

最后，还有关键的一步，就是把当前总和的前缀和进行回溯，因为我们的前缀和只对子节点范围内的子树是有效的，如果我们不及时回溯，可能会影响同层节点的的路径统计，其他同层节点的路径统计可能会误用到我们当前节点产生的前缀和。

        //回溯前缀和，防止影响其他节点的遍历map.put(curSum,map.getOrDefault(curSum,0)-1);

完成回溯之后，将统计到的次数进行返回即可。

        //返回结果return result;

3.代码展示

/*** 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) {//记录目标前缀和与对应个数的映射关系Map<Long,Integer> map = new HashMap<>();//初始化map，前缀和为0的个数为1个map.put(0L,1);//递归求路径数目return preOrder(root,targetSum,0,map);}public int preOrder(TreeNode root,int targetSum,long curSum,Map<Long,Integer> map){//如果是空节点，直接返回0if(root == null){return 0;}//存储目标次数int result = 0;//累加当前总和curSum += root.val;//从map中获取前缀和result += map.getOrDefault(curSum - targetSum,0);//更新当前总和出现的次数map.put(curSum,map.getOrDefault(curSum,0)+1);//递归遍历左子树int left = preOrder(root.left,targetSum,curSum,map);//递归遍历右子树int right = preOrder(root.right,targetSum,curSum,map);//累加左右子树出现的目标次数result += (left+right);//回溯当前累加总和出现的次数，防止对其他遍历过程造成影响map.put(curSum,map.getOrDefault(curSum,0)-1);//返回结果return result;}
}