给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出:true 解释:等于目标和的根节点到叶节点路径如上图所示。
/**
* 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 {
public boolean hasPathSum(TreeNode root, int targetSum) {
// 如果根节点为空,则返回false
if (root == null) return false;
// 如果当前节点是叶子节点,且节点值等于目标和,则返回true
if (root.left == null && root.right == null && targetSum == root.val) {
return true;
}
// 递归检查左子树
boolean leftPathSum = false;
if (root.left != null) {
leftPathSum = hasPathSum(root.left, targetSum - root.val);
}
// 递归检查右子树
boolean rightPathSum = false;
if (root.right != null) {
rightPathSum = hasPathSum(root.right, targetSum - root.val);
}
// 返回左右子树的结果
return leftPathSum || rightPathSum;
}
}
回溯更好的展现出来
/**
* 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 {
public boolean tral(TreeNode root,int count){
if(root==null) return false;
if(root.left==null&&root.right==null&&count==0) return true;
if(root.left!=null){
count-=root.left.val;
if(tral(root.left,count)) return true;
count+=root.left.val;//回溯
}
if(root.right!=null){
count-=root.right.val;
if(tral(root.right,count)) return true;
count+=root.right.val;//回溯
}
return false;
}
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
return tral(root,targetSum-root.val);
}
}
给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]]
提示:
- 树中节点总数在范围
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
/**
* 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 {
public void travelsal(TreeNode root,int count,List<List<Integer>> result,List<Integer> path){
if(root==null) return;
path.add(root.val);//这里将遍历的节点值添加到path中
if(root.left == null&&root.right==null&&count-root.val==0) result.add(new ArrayList<>(path));
if(root.left!=null){
//这里就不用add了
travelsal(root.left,count-root.val,result,path);
}
if(root.right!=null){
//这里就不用add了
travelsal(root.right,count-root.val,result,path);
}
path.remove(path.size()-1);//回溯,移除当前节点,恢复路径状态!!!!!!
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
if(root==null) return result;
List<Integer> path = new ArrayList<>();
travelsal(root,targetSum,result,path);
return result;
}
}