LeetCode算法题-Path Sum III(Java实现)
这是悦乐书的第227次升级
01 看题和准备
今天详情的是LeetCode算法题中Easy级别的第94题(顺位题号是437)。您将取得一个二叉树,其中每个节点都包含一个整数值。找到与给定值相加的路径数。路径不需要在根或者叶子处开始或者结束,但必需向下(仅从父节点行进到子节点)。树的节点数不超过1,000个,值范围为-1,000,000到1,000,000。例如:
root = [10,5,-3,3,2,null,11,3,-2,null,1],sum = 8
10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
返回3。总和为8的路径为:
1、5 – > 3
2、5 – > 2 – > 1
3、-3 – > 11
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
使用深度优先算法(DFS),由于题目说可以在任意节点开始,可以在任意节点结束,因而在开始位置有两个选择:从根节点开始;从根节点的子节点开始。而从根节点的子节点开始,此子问题和问题本身性质一样,需要调用自身。而从根节点开始,则需要调用另外一个方法,此方法同样是两个参数,当前节点和sum。
定义一个记数变量,记录可能的路径数。假如当前节点为null,返回0。假如当前节点值和sum相等,记数加1,同时对于当前节点的左节点、右节点继续调用此方法,而第二个参数sum,则需要减掉当前节点的值。
public int pathSum(TreeNode root, int sum) { if (root == null) { return 0; } return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);}public int findPath(TreeNode root, int sum) { int result = 0; if (root == null) { return result; } if (sum == root.val) { result++; } result += findPath(root.left, sum-root.val); result += findPath(root.right, sum-root.val); return result;}
03 第二种解法
此解法来自探讨区。对于树中的每个父节点,我们有两个选择:
1.将它包括在达到总和的路径中。
2.不要将其包含在达到总和的路径中。
对于树中的每个子节点,我们有2个选择:
1.取走父节点留给你的东西。
2.从自己开始形成路径。
传送门:https://leetcode.com/problems/path-sum-iii/discuss/91996/Easy-to-understand-Java-solution-with-comment.
int target;Set<TreeNode> visited;public int pathSum2(TreeNode root, int sum) { target = sum; //to store the nodes that have already tried to start path by themselves. visited = new HashSet<TreeNode>(); return pathSumHelper(root, sum, false);}public int pathSumHelper(TreeNode root, int sum, boolean hasParent) { if(root == null) return 0; //the hasParent flag is used to handle the case when parent path sum is 0. //in this case we still want to explore the current node. if (sum == target && visited.contains(root) && !hasParent) { return 0; } if (sum == target && !hasParent) { visited.add(root); } int count = (root.val == sum) ? 1 : 0; count += pathSumHelper(root.left, sum - root.val, true); count += pathSumHelper(root.right, sum - root.val, true); count += pathSumHelper(root.left, target , false); count += pathSumHelper(root.right, target, false); return count;}
04 第三种解法
此解法同样来自探讨区,使用HashMap来操作。
传送门:https://leetcode.com/problems/path-sum-iii/discuss/91878/17-ms-O(n)-java-Prefix-sum-method
public int pathSum3(TreeNode root, int sum) { Map<Integer, Integer> map = new HashMap<>(); //Default sum = 0 has one count map.put(0, 1); return backtrack(root, 0, sum, map); }public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map){ if (root == null) { return 0; } sum += root.val; //See if there is a subarray sum equals to target int res = map.getOrDefault(sum - target, 0); map.put(sum, map.getOrDefault(sum, 0)+1); //Extend to left and right child res += backtrack(root.left, sum, target, map); res += backtrack(root.right, sum, target, map); //Remove the current node so it won't affect other path map.put(sum, map.get(sum)-1); return res;}
05 小结
算法专题目前已连续日更超过两个月,算法题文章94+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Path Sum III(Java实现)