本文共 2501 字，大约阅读时间需要 8 分钟。

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

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

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 {    int count = 0;    public int pathSum(TreeNode root, int targetSum) {        if (root == null) {            return 0;        }        sum(root,targetSum);//查找根节点是否存在路径        pathSum(root.left,targetSum);//继续遍历左子树        pathSum(root.right,targetSum);//继续遍历右子树        return count;    }    public void sum(TreeNode node,int targetSum) {        if (node == null) {            return;        }        targetSum -= node.val;        if (targetSum == 0) {//如果减去当前节点后，目标值变为了0，就说明找到了一条路径            count++;        }        //目标值不为0的情况，说明当前节点不是最终节点        sum(node.left,targetSum);//往左子树上找        sum(node.right,targetSum);//往右子树上找    }}

2.上面这种方法会产生很多重复计算，可以进一步优化。前缀和思想。

        参考：

        存储根节点到每个节点的路径和，并且把到该节点之前的可能的前缀路径和存储下来，然后

      查找是否存在路径前缀和为currentSum-targetSum，如果存在的话那么这条前缀和的终点节点

      就是要寻找的目标路径的起点，该起点到当前节点的路径和就是targetSum。

class Solution {    //存储前缀和(从根节点到当前节点的路径和)，key是前缀和，value是该前缀和路径的数量    Map
   
     prefixSumCount = new HashMap<>();    public int pathSum(TreeNode root, int targetSum) {        prefixSumCount.put(0,1);//初始化，前缀和为1的路径有1条        return recursionPathSum(root,targetSum,0);    }    public int recursionPathSum(TreeNode node,int targetSum,int currentSum) {        if (node == null) {            return 0;        }        int count = 0;//路径和        currentSum += node.val;//计算根节点到当前节点的路径和        //判断之前是否有和为currentSum - targetSum的路径，如果有的话，就能找到起点        count += prefixSumCount.getOrDefault(currentSum - targetSum,0);//这一句是判断当前节点是不是要求路径的终点        prefixSumCount.put(currentSum,prefixSumCount.getOrDefault(currentSum,0) + 1);//把当前前缀和也存储起来        count += recursionPathSum(node.left,targetSum,currentSum);//继续查找左子树        count += recursionPathSum(node.right,targetSum,currentSum);//继续查找右子树        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);//回溯，把当前前缀路径去掉        return count;    }}
   

题源：

转载地址：https://blog.csdn.net/xxyneymar/article/details/122232516 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！