路径总和
题目描述(题目链接)
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false
示例 3：
输入：root = [1,2], targetSum = 0 输出：false
提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
分析
对于这种判断的，只要有一个满足条件的即可，在遍历路径上肯定使用dfs遍历。向下一层的时候就处理一下当前层的值，这样有一个满足的结果那么就可以返回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) { if(root==null) return false; int value=targetSum-root.val; if(root.left==null&&root.right==null) { if(value==0) return true; } else { return hasPathSum(root.left,value)||hasPathSum(root.right, value); } return false; } }
路径总和Ⅱ
题目描述(题目链接)
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ]
分析：
这个问题就是要求返回所有满足要求的结果，和上题略有不同就是需要找到所有结果并且保存，保存结果的话我们就需要一个List<Integer>存储遍历的结果,而List<List<Integer>>用来存储所有的结果，所以在递归回溯的过程中就需要借助回溯的过程经过每一个状态，满足状态的就将这个List复制到结果集中去，需要返回的时候还需要移除当前层加入的结果。
具体实现的代码为：
/** * 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 { List<Integer> team = new ArrayList<Integer>(); List<List<Integer>> value = new ArrayList<List<Integer>>(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { if (root == null) return value; team.add(root.val); targetSum-=root.val; if(targetSum==0&&root.left==null&&root.right==null) { value.add(new ArrayList<Integer>(team)); } pathSum(root.left, targetSum); pathSum(root.right, targetSum); team.remove(team.size()-1); return value; } }
原创不易，bigsai请你帮两件事帮忙一下:
star支持一下， 您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
