移动终端的网站,百度小程序在哪里找,泰安市建设职工培训中心网站进不去,无锡网建公司java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 深度优先2. 前缀和 1. 深度优先
解题思路#xff1a;时间复…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 深度优先2. 前缀和 1. 深度优先
解题思路时间复杂度O( n 2 n^2 n2),空间复杂度O(n) 从最下层结点开始以每个结点为根结点再次从上到下深度优先遍历试图找到符合条件的路径很显然是双重深度优先遍历先深度优先遍历所有结点然后每个结点还得再深度优先遍历一下找路径所以是N^2时间复杂度 代码 class Solution {//计算路径和public int pathSum(TreeNode root, int targetSum) {if (root null) {return 0;}//获取以当前为根结点的路径和int ret rootSum(root, targetSum);//深度优先遍历ret pathSum(root.left, targetSum);ret pathSum(root.right, targetSum);return ret;}//计算当前根结点的路径和对于每个结点都进行从上到下的深度优先遍历//看看有没有符合条件的路径-------穷举法public int rootSum(TreeNode root, long targetSum) {int ret 0;//深度优先记录符合条件的路径数目if (root null) {return 0;}int val root.val;//获取当前结点值if (val targetSum) {//如果当前值 targetSum 结果1注意这里targetSum是减去前面结点还需要多少ret;} //深度优先传入targetSum - 当前结点值还需要多少ret rootSum(root.left, targetSum - val);//左子树符合条件的ret rootSum(root.right, targetSum - val);//右子树符合条件的return ret;//返回当前结点符合条件的}
}2. 前缀和
解题思路时间复杂度O(n),空间复杂度O(n).其中空间复杂度是2n因为需要一个map深度优先遍历需要栈空间也是n所以是2n时间复杂度比上一个方法的空间复杂度多一倍。但是时间复杂度比它快n倍 深度优先遍历遍历过程中记录前缀和就是从根结点到当前结点的和到map中每遍历一个结点都用当前前缀和 - 目标值看看差多少并从map中找这个差值 如果找到这个差值说明当前前缀 - 当前路径上的某个子前缀是一个符合条件的路径如果没有说明没找到继续向下遍历 当某个结点深度遍历完成向上返回时那么包含这个结点的前缀和就没有用了需要从map中去掉 图解找目标路径长度为8 初始状态下前缀mapkey保存前缀0value保存此前缀有几个为1 深度遍历根结点10则当前路径前缀长度为1010 - 8 2也就是当前前缀比目标值多2.不符合条件。继续深度优先遍历并将当前前缀和10放入map此前缀有目前有1个 深度遍历到结点5当前路径前缀和为15,15-8 7map中找7找不到所以将15:1放入map 继续遍历到结点3当前路径前缀和为18,18 - 8 10.此时map中发现10也就是说当前路径比目标值8多10而10就在此路径的子前缀中所以我们可以去掉10这个结点这样我们就找到了第一个符合条件的路径5和3。另外不要忘了将当前前缀和放入map也就是18:1放入map 继续向下遍历结点3此时发现前缀和为21,21 - 8 13map中没有放入前缀和21:1 继续向下我们发现已经到底需要回溯了回到父结点之前需要先删除当前前缀和21:1然后再回父结点。之后继续遍历重复上述步骤。 代码: 官方增加了测试用例所以相同的代码已经无法击败100%了 class Solution {public int pathSum(TreeNode root, int targetSum) {MapLong, Integer prefix new HashMapLong, Integer();//用Map保存前缀和prefix.put(0L, 1);//初始放入前缀和0和其1return dfs(root, prefix, 0, targetSum);//进入递归}public int dfs(TreeNode root, MapLong, Integer prefix, long curr, int targetSum) {if (root null) return 0;int ret 0;//符合条件的路径条数curr root.val;//当前路径值前缀和//看看当前路径和 - 目标值是否等于路径上的一个前缀//如果是的话说明当前路径去掉某些前缀结点刚好符合targetSum//如果没有那么ret依然是0ret prefix.getOrDefault(curr - targetSum, 0);//将当前路径前缀和加入到map中prefix.put(curr, prefix.getOrDefault(curr, 0) 1);//深度优先ret dfs(root.left, prefix, curr, targetSum);ret dfs(root.right, prefix, curr, targetSum);//----------当此结点的遍历出栈时要将map中对应的前缀和去掉。否则其它路径的前缀和很可能和当前路径的前缀和冲突-------------prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);//返回符合条件路径条数return ret;}
}
