一、题目概述
二、思路方向
为了解决这个问题,我们可以使用深度优先搜索(DFS)算法来遍历二叉树,并检查从根节点到叶子节点的路径和是否等于目标和。
三、代码实现
java">class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }
} public class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { // 如果根节点为空,则无法找到路径 if (root == null) { return false; } // 如果当前节点是叶子节点,则检查当前节点的值是否等于目标和 if (root.left == null && root.right == null) { return root.val == targetSum; } // 递归地在左子树和右子树中查找路径和 // 减去当前节点的值,将剩余的目标和传递给子树 return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } public static void main(String[] args) { // 示例用法 TreeNode root = new TreeNode(5); root.left = new TreeNode(4); root.right = new TreeNode(8); root.left.left = new TreeNode(11); root.left.left.left = new TreeNode(7); root.left.left.right = new TreeNode(2); root.right.left = new TreeNode(13); root.right.right = new TreeNode(4); root.right.right.right = new TreeNode(1); Solution solution = new Solution(); boolean result = solution.hasPathSum(root, 22); System.out.println("Does the path exist? " + result); // 应该输出 true result = solution.hasPathSum(root, 20); System.out.println("Does the path exist? " + result); // 应该输出 false }
}
执行结果:
四、小结
这段代码首先定义了一个
TreeNode
类来表示二叉树的节点。然后,在Solution
类中定义了一个hasPathSum
方法,该方法接收二叉树的根节点和一个目标和targetSum
作为参数。该方法使用递归的方式遍历二叉树,在遍历过程中不断减去当前节点的值,直到遇到叶子节点时检查剩余的目标和是否为零。如果在某条路径上,从根节点到叶子节点的所有节点值之和等于目标和,则返回true
;如果遍历完所有路径都没有找到符合条件的路径,则返回false
。在
main
方法中,我们创建了一个示例二叉树,并调用hasPathSum
方法来检查是否存在路径和等于特定值的情况,并打印结果。
结语
勤奋是你生命的密码
能译出你一部壮丽的史诗
!!!