路径总和
难度:
标签:
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
代码结果
运行时间: 44 ms, 内存: 16.6 MB
// Java solution using Stream for the problem
// The function checks if there is a path from root to leaf with the sum equal to targetSum.
import java.util.stream.Stream;
public class SolutionStream {
// TreeNode definition remains the same as in the Java solution
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
return Stream.of(root.left, root.right)
.filter(node -> node != null)
.anyMatch(node -> hasPathSum(node, targetSum - root.val));
}
}
解释
方法:
这个题解采用递归的方式来判断是否存在根节点到叶子节点的路径，其和等于目标值。具体思路如下：
1. 如果当前节点为空，返回False，因为空树不存在满足条件的路径。
2. 如果当前节点是叶子节点（即左右子节点都为空），判断当前节点的值是否等于目标值，如果相等则找到了一条满足条件的路径，返回True；否则返回False。
3. 如果当前节点不是叶子节点，则递归地在其左子树和右子树中查找是否存在满足条件的路径。在递归时，将目标值减去当前节点的值，这样就可以在子树中继续判断剩余的目标值是否能够由根节点到叶子节点的路径所满足。
4. 如果在左子树或右子树中任一找到满足条件的路径，就返回True；只有当左右子树都不存在满足条件的路径时，才返回False。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归的过程中，当遇到一个节点值大于当前目标和（targetSum - 当前节点的值为负数）时，是否还有必要继续探索该节点的子树？
▷🦆
题解中提到递归时要减去当前节点的值，这个操作对于处理负权值的节点有什么影响？能否正确处理所有包含负值节点的情况？
▷🦆
对于非常大或非常小的targetSum值，递归解法是否仍然有效，或者会遇到数值溢出的问题？
▷🦆
在递归函数中，如果左子树找到了满足条件的路径，是否还需要继续检查右子树？
▷相关问题
路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
求根节点到叶节点数字之和
给你一个二叉树的根节点
root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径1->2代表数字12从根到叶子节点路径1->3代表数字13因此，数字总和 = 12 + 13 =25
示例 2：
输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径4->9->5代表数字 495 从根到叶子节点路径4->9->1代表数字 491 从根到叶子节点路径4->0代表数字 40 因此，数字总和 = 495 + 491 + 40 =1026
提示：
- 树中节点的数目在范围
[1, 1000]内 0 <= Node.val <= 9- 树的深度不超过
10
路径总和 III
给定一个二叉树的根节点 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