Java算法题-解析 路径总和 算法问题
题目:
给定一个二叉树和一个目标和,判断是否存在从根节点到叶子节点的路径,使得路径上的节点值之和等于目标和。
引言:
路径总和问题涉及到在二叉树中寻找从根节点到叶子节点的路径,并验证路径上节点值之和是否等于给定的目标值。这个问题在树的遍历中很常见,可以使用深度优先搜索(DFS)来解决。
算法思路:
- 定义一个递归函数
hasPathSum
,该函数接受一个二叉树节点和一个目标和作为参数,并返回一个布尔值,表示是否存在路径满足目标和。 - 在每个节点上,递归调用
hasPathSum
函数来判断左子树和右子树中是否存在路径满足目标和。 - 在递归的过程中,每次将目标和减去当前节点的值。
- 如果当前节点是叶子节点(即没有左子树和右子树),则检查目标和是否等于当前节点的值,如果相等则返回 true,否则返回 false。
代码实现:
以下是使用 Java 实现的解决方案:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class PathSum {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
// 当前节点是叶子节点且值等于目标和,返回 true
if (root.left == null && root.right == null && root.val == targetSum) {
return true;
}
// 递归检查左子树和右子树
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
public static void main(String[] args) {
PathSum solution = new PathSum();
// 创建一个示例二叉树
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;
boolean hasPath = solution.hasPathSum(root, targetSum);
System.out.println("是否存在路径满足目标和 " + targetSum + ": " + hasPath);
}
}
算法分析:
- 时间复杂度:对于每个节点,我们只需遍历一次,因此时间复杂度是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) {
PathSum solution = new PathSum();
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;
boolean hasPath = solution.hasPathSum(root, targetSum);
System.out.println("是否存在路径满足目标和 " + targetSum + ": " + hasPath);
}
}
总结:
路径总和问题是一个常见的二叉树遍历问题,通过使用深度优先搜索(DFS)来遍历二叉树,同时更新目标和,可以有效地解决这个问题。这个算法的时间复杂度是O(n),空间复杂度是O(h),其中n是二叉树的节点数,h是二叉树的高度。解决这个问题有助于理解二叉树的路径和性质,以及如何使用递归来处理树结构。