路径总和 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
代码结果
运行时间: 756 ms, 内存: 16 MB
/*
* 思路：
* 由于 Java Stream 主要用于处理集合数据，二叉树的结构不适合使用流式处理。
* 这里使用传统递归方法计算路径数。
* 我们可以定义一个树的遍历方法来使用流式 API 生成节点集合。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
List<TreeNode> nodes = new ArrayList<>();
traverseTree(root, nodes);
return nodes.stream()
.mapToInt(node -> pathSumFromNode(node, targetSum))
.sum();
}
private void traverseTree(TreeNode node, List<TreeNode> nodes) {
if (node == null) return;
nodes.add(node);
traverseTree(node.left, nodes);
traverseTree(node.right, nodes);
}
private int pathSumFromNode(TreeNode node, int sum) {
if (node == null) return 0;
int count = 0;
if (node.val == sum) count++;
count += pathSumFromNode(node.left, sum - node.val);
count += pathSumFromNode(node.right, sum - node.val);
return count;
}
}解释
方法:
这个题解采用递归的方式对二叉树进行深度优先遍历。主函数 pathSum 递归调用自身，分别以根节点的左右子节点作为新的根节点，继续寻找满足条件的路径。在每次调用 pathSum 时，都会调用 helper 函数，helper 函数则从当前节点开始，使用 dfs 函数进行路径搜索。dfs 函数会在找到一条满足条件的路径时，将 ret 计数器加1，然后继续搜索左右子树，寻找更多可能的路径。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到了对每个节点使用dfs进行搜索，请问这种方法是否会导致某些路径被重复计算？如果是，如何避免重复计算？
▷🦆
在解题思路中，helper函数和dfs函数的区别和联系是什么？helper具体是如何利用dfs函数来实现功能的？
▷🦆
题解中的dfs函数在遍历到null节点时直接返回，这种处理方式是否会影响对非叶子节点路径的计数？
▷🦆
题解中没有明确说明如何处理节点值为负数的情况，负数节点值会对寻找路径和计算路径和带来哪些挑战？
▷相关问题
路径总和
给你二叉树的根节点 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
路径总和 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
