给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。 叶子节点 是指没有子节点的节点。 java
时间: 2025-02-16 12:14:49 浏览: 34
这是一个经典的深度优先搜索(DFS)问题,可以使用递归的方式来解决。首先,我们需要定义一个辅助方法来检查给定节点的值加上它的左右子节点的和是否等于目标和。如果找到这样的路径,则返回 true ,否则继续向下遍历。如果到了叶子节点(子节点为空),仍然没有达到目标和,那么就返回 false 。
以下是 Java 代码示例:
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
// constructor, getters and setters...
}
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false; // 如果根节点为空,直接返回
// 递归检查左子树和右子树
boolean leftSum = hasPathSum(root.left, targetSum - root.val);
boolean rightSum = hasPathSum(root.right, targetSum - root.val);
// 如果目标和等于当前节点值,或者通过左右子树找到了满足条件的路径,返回 true
return (targetSum == root.val || leftSum || rightSum);
}
```
在这个代码中,我们先检查根节点的值是否就是目标和,如果不是,我们就尝试将目标和减去当前节点的值,并在左子树和右子树中分别查找是否有满足条件的路径。如果在任意一侧找到,说明存在路径,返回 true;否则,返回 false。
阅读全文
相关推荐

















