大家好！我是曾续缘💫
今天是《LeetCode 热题 100》系列
发车第 48 天
二叉树第 13 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给定一个二叉树的根节点 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]
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000
难度：💖💖

解题方法

题目要求我们找出二叉树中所有节点值之和等于给定整数 targetSum 的路径数目。这里的路径不需要从根节点开始，也不需要在叶子节点结束，但路径必须是向下的，即只能从父节点到子节点。

我们可以采用递归的方法来解决这个问题。主要分为两个步骤：

从根节点开始递归：计算从当前节点开始，所有可能路径的节点值之和等于 targetSum 的路径数目。
递归左右子树：对于每个节点，除了计算从该节点开始的路径数目外，还需要递归计算其左右子树中满足条件的路径数目。

具体步骤如下：

定义一个辅助函数 count_from_root，用于计算从当前节点开始，所有可能路径的节点值之和等于 targetSum 的路径数目。
在 count_from_root 函数中，递归计算当前节点、左子节点和右子节点的路径数目，并将结果累加。
在 pathSum 函数中，首先判断当前节点是否为空，如果为空则返回 0。否则，返回从当前节点开始的路径数目（通过 count_from_root 函数计算）加上左右子树中满足条件的路径数目（通过递归调用 pathSum 函数计算）。

这种方法的时间复杂度是 $O (n^{2})$ 。

Code

查看代码

java

/**
 * 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 count_from_root(TreeNode root, long sum){
        if(root == null){
            return 0;
        }
        int cnt = 0;
        if(sum == root.val)cnt++;
        cnt += count_from_root(root.left, sum - root.val);
        cnt += count_from_root(root.right, sum - root.val);
        return cnt; 
    }
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){
            return 0;
        }
        return count_from_root(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }
}

解题方法 ​

Code ​

解题方法

Code