一、目标
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。
叶子节点 是指没有子节点的节点。
二、代码解读
总体代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//初始化判断标志位成员变量
private boolean judge = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
ArrayList<Integer> paths = new ArrayList<>();
//防止直接传入空节点
if(root == null){
return false;
}
getpaths(paths, root, targetSum);
//返回标志位
return judge;
}
public void getpaths(ArrayList<Integer> paths, TreeNode root, int targetSum){
//getpaths方法由二叉树所有路径题目代码改编而成,详细主页,只解释修改部分
paths.add(root.val);
if(root.left == null && root.right == null){
/*每次判断到一个叶子节点代表着记录完一条路径,
求出该条路经的和,判断是否与targetSum相同,
如果相同更细标志位为true
*/
int sum = 0;
for(int i : paths){
sum += i;
}
if(sum == targetSum){
judge = true;
}
}
if(root.left != null){
getpaths(paths, root.left, targetSum);
paths.remove(paths.size() - 1);
}
if(root.right != null){
getpaths(paths, root.right, targetSum);
paths.remove(paths.size() - 1);
}
}
}
主要流程为初始化标志位false,空节点传入判断,记录二叉树所有路径的同时只进行路径临时储存,每次找到一条路径求一次和判断一次是否要更新标志位为true
public void getpaths(ArrayList<Integer> paths, TreeNode root, int targetSum){
//getpaths方法由二叉树所有路径题目代码改编而成,详细主页,只解释修改部分
paths.add(root.val);
if(root.left == null && root.right == null){
/*每次判断到一个叶子节点代表着记录完一条路径,
求出该条路经的和,判断是否与targetSum相同,
如果相同更细标志位为true
*/
int sum = 0;
for(int i : paths){
sum += i;
}
if(sum == targetSum){
judge = true;
}
}
if(root.left != null){
getpaths(paths, root.left, targetSum);
paths.remove(paths.size() - 1);
}
if(root.right != null){
getpaths(paths, root.right, targetSum);
paths.remove(paths.size() - 1);
}
}
三、总结
本题解法基于二叉树所有路径的解法上修改而成,可以视作是一道题一起进行记忆。
标签:paths,right,JAVA,int,力扣,targetSum,112,TreeNode,root From: https://blog.csdn.net/zzb1580/article/details/143634931