import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param targetSum int整型
* @return bool布尔型
*/
public boolean hasPathSum (TreeNode root, int targetSum) {
// write code here
// 当前节点为空,返回false
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);
}
}
该Java代码使用的编程语言是Java。
该题考察的知识点有:
- 二叉树的遍历:通过递归的方式对二叉树进行深度优先搜索(DFS)遍历。
- 递归:通过递归的方式实现深度优先搜索,从根节点开始递归地遍历左子树和右子树。
- 叶子节点的判断:通过判断节点的左子节点和右子节点是否为空,确定节点是否为叶子节点。
- 方法的定义和使用:通过定义一个方法
hasPathSum,传入根节点和目标和来判断路径和是否等于目标和。 - 逻辑判断和返回值:通过判断当前节点和子节点的情况,确定是否存在路径和等于目标和,并返回相应的结果。
代码解释如下:
- 定义了一个树节点类
TreeNode,包含一个整型变量val表示节点的值,以及左右子节点的引用。 - 定义了一个类
Solution,其中包含了一个方法hasPathSum,用于判断二叉树中是否存在一条路径的节点值之和等于目标和。 - 在
hasPathSum方法中,先判断当前节点是否为空,如果为空,则返回false,表示不存在这样的路径。 - 如果当前节点是叶子节点,即左右子节点均为空,判断当前节点的值是否等于目标和,如果相等则返回true,表示存在这样的路径。
- 如果当前节点不是叶子节点,递归调用
hasPathSum方法,分别传入左子树和右子树以及目标和减去当前节点值,判断左子树或右子树是否存在路径和等于目标和。 - 最后返回左子树和右子树判断的结果中的任意一个,只要存在一条路径和等于目标和,就返回true,否则返回false。
在整个遍历过程中,通过递归实现了二叉树的深度优先搜索,判断了路径和是否等于目标和。

京公网安备 11010502036488号