Java算法题-解析路径总和II问题
题目
给定一个二叉树和一个目标和，找出所有从根节点到叶子节点的路径，这些路径上的节点值之和等于目标和。
引言
路径总和II问题是一个与路径和相关的常见问题。与路径和问题不同，路径总和II需要找出所有满足条件的路径，而不仅仅是判断是否存在一条路径。
在这个问题中，我们要找出从根节点到叶子节点的所有路径，这些路径的节点值之和等于给定的目标和。我们可以使用回溯法来解决这个问题。
算法思路
- 定义一个递归函数
findPaths，该函数接受当前节点node、目标和target、当前路径currentPath、结果集result作为参数。 - 在每个节点上，将当前节点的值添加到
currentPath中。 - 如果当前节点是叶子节点且节点值等于目标和，将
currentPath添加到result中。 - 递归调用
findPaths函数来分别处理左子树和右子树。 - 回溯：在返回上一级之前，从
currentPath中移除当前节点的值。 - 最终，返回
result，其中包含所有满足条件的路径。
代码实现
以下是使用 Java 实现的解决方案：
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class PathSumII {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
findPaths(root, targetSum, currentPath, result);
return result;
}
private void findPaths(TreeNode node, int target, List<Integer> currentPath, List<List<Integer>> result) {
if (node == null) {
return;
}
currentPath.add(node.val);
if (node.left == null && node.right == null && target == node.val) {
// 当前节点是叶子节点且值等于目标和，将当前路径添加到结果中
result.add(new ArrayList<>(currentPath));
} else {
// 递归查找左子树和右子树
findPaths(node.left, target - node.val, currentPath, result);
findPaths(node.right, target - node.val, currentPath, result);
}
// 回溯：移除当前节点，返回上一级
currentPath.remove(currentPath.size() - 1);
}
public static void main(String[] args) {
PathSumII solution = new PathSumII();
// 创建一个示例二叉树
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.right.right = new TreeNode(1);
int targetSum = 22;
List<List<Integer>> paths = solution.pathSum(root, targetSum);
// 打印结果
for (List<Integer> path : paths) {
System.out.println("路径: " + path);
}
}
}算法分析
- 时间复杂度：对于每个节点，我们只需遍历一次，因此时间复杂度是O(n)，其中n是二叉树的节点数。
- 空间复杂度：递归调用栈的深度最多为树的高度，所以空间复杂度是O(h)，其中h是二叉树的高度。
示例和测试
假设给定一个示例二叉树 root 和目标和 targetSum，如下所示：
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1根据算法，我们可以找到所有满足条件的路径。我们可以使用以下代码进行测试：
public class Main {
public static void main(String[] args) {
PathSumII solution = new PathSumII();
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.right.right = new TreeNode(1);
int targetSum = 22;
List<List<Integer>> paths = solution.pathSum(root, targetSum);
// 打印结果
for (List<Integer> path : paths) {
System.out.println("路径: " + path);
}
}
}总结
路径总和II问题要求找出所有满足条件的路径，这些路径的节点值之和等于给定的目标和。我们使用回溯法来解决这个问题，递归遍历树的每个节点，同时更新当前路径和目标和，当找到满足条件的路径时，将其添加到结果中。这个算法的时间复杂度是O(n)，空间复杂度是O(h)，其中n是二叉树的节点数，h是二叉树的高度。解决这个问题有助于理解回溯算法在树结构中的应用。
