路径总和 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
代码结果
运行时间: 56 ms, 内存: 16.2 MB
/*
* Problem: Same as above, but using Java Stream API for a more functional programming approach.
* We'll use helper functions to handle the recursive path finding.
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class SolutionWithStreams {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
return findPaths(root, targetSum, new ArrayList<>());
}
private List<List<Integer>> findPaths(TreeNode node, int targetSum, List<Integer> currentPath) {
if (node == null) {
return new ArrayList<>();
}
currentPath.add(node.val);
if (node.left == null && node.right == null && targetSum == node.val) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>(currentPath));
return result;
}
List<List<Integer>> leftPaths = findPaths(node.left, targetSum - node.val, new ArrayList<>(currentPath));
List<List<Integer>> rightPaths = findPaths(node.right, targetSum - node.val, new ArrayList<>(currentPath));
leftPaths.addAll(rightPaths);
return leftPaths;
}
}
解释
方法:
该题采用深度优先搜索(DFS)的方法。从根节点开始，遍历整棵二叉树，并记录从根到当前节点的路径。当遍历到叶子节点，且路径上节点值的总和等于目标和时，将该路径加入结果列表。在递归回溯时，要从路径中删除当前节点，以便尝试其他路径。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在递归函数中使用了`path.append(root.val)`和`path.pop()`，这样的操作有什么特别的意义或好处？
▷🦆
代码中的条件`if root.val == k and root.left is None and root.right is None`是否充分确保了只在叶子节点处检查路径总和？如果在非叶子节点满足条件会有什么后果？
▷🦆
如果树的所有节点值都大于0，且targetSum是一个负数，这种情况下算法的行为是什么？
▷🦆
给定的解法是基于深度优先搜索（DFS），这种方法与广度优先搜索（BFS）相比在处理这类问题上有什么优缺点？
▷相关问题
路径总和
给你二叉树的根节点 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
二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
路径总和 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