力扣hot100 路径总和Ⅲ dfs 前缀和 一题双解 超全注释

这篇具有很好参考价值的文章主要介绍了力扣hot100 路径总和Ⅲ dfs 前缀和 一题双解 超全注释。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem: 437. 路径总和 III

力扣hot100 路径总和Ⅲ dfs 前缀和 一题双解 超全注释,力扣 hot100,深度优先,leetcode,算法

思路

树的遍历 + DFS
一个朴素的做法是搜索以每个节点为根的(往下的)所有路径,并对路径总和为 targetSumtargetSumtargetSum 的路径进行累加统计。

使用 dfs1 来搜索所有节点,复杂度为 O(n)O(n)O(n);在 dfs1 中对于每个当前节点,使用 dfs2 搜索以其为根的所有(往下的)路径,同时累加路径总和为 targetSumtargetSumtargetSum 的所有路径,复杂度为 O(n)O(n)O(n)。

👨‍🏫 参考题解

💖 树的遍历 + dfs

时间复杂度, 示例: O ( n 2 ) O(n^2) O(n2)

/**
 * 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 {
	long ans, t;// ans 统计符合要求的路径数量,t 记录目标值

	public int pathSum(TreeNode root, int targetSum)
	{
		t = targetSum;
		dfs1(root);
		return (int) ans;

	}

//	遍历 root 的所有子结点
	private void dfs1(TreeNode root)
	{
		if (root == null)
			return;
		dfs2(root, root.val);
		dfs1(root.left);
		dfs1(root.right);
	}

//	以 root 为根遍历其所有合法路径
	private void dfs2(TreeNode root, long val)
	{
		if (val == t)// 如果当前路径和恰好 == 目标值 ans++
			ans++;
		if (root.left != null)// 向左子树延申路径
			dfs2(root.left, val + root.left.val);
		if (root.right != null)// 向右子树延申路径
			dfs2(root.right, val + root.right.val);
	}
}

💖 树的遍历 + 前缀和

👨‍🏫 参考题解

时间复杂度, 示例: O ( n ) O(n) O(n)
从根节点到每个叶子结点的路径唯一,这就是一个前缀和文章来源地址https://www.toymoban.com/news/detail-783376.html

/**
 * 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 {
	long ans, t;// ans 统计符合要求的路径数量,t 记录目标值

//	注意:map集合只会包含当前结点的 祖先结点 的前缀和(在递归的过程种进行恢复现场)
	Map<Long, Integer> map = new HashMap<>();// key是前缀和,value是前缀和为key的结点数量

	public int pathSum(TreeNode root, int target)
	{
		if (root == null)
			return 0;
		t = target;
		map.put(0L, 1);
		dfs(root, root.val);
		return (int) ans;
	}

	/**
	 * @param root 当前根节点
	 * @param val  以当前root为尾结点的前缀和(此值唯一)
	 */
	private void dfs(TreeNode root, long val)
	{
		// 当前点前缀和(val) - 前边点的前缀和(map的key) == t
		// key = val - t,此 key 存在,证明前缀和可以实现
		if (map.containsKey(val - t))
			ans += map.get(val - t);
		map.put(val, map.getOrDefault(val, 0) + 1);//把当前点的前缀和作为 key 存进 map中
//		递归遍历当前树的左右子树
		if (root.left != null)
			dfs(root.left, val + root.left.val);
		if (root.right != null)
			dfs(root.right, val + root.right.val);
//		把当前点的前缀和作为 key 从 map 中取出,因为上边两个递归已经把它的子树(后代节点)都处理完了(留着也没用)
//		恢复现场:当前分支产生的影响不应该干扰到当前结点的兄弟分支的结果
		map.put(val, map.getOrDefault(val, 0) - 1);
	}
}

到了这里,关于力扣hot100 路径总和Ⅲ dfs 前缀和 一题双解 超全注释的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣 113. 路径总和 II

    题目来源:https://leetcode.cn/problems/path-sum-ii/description/   C++题解:采用递归法,前序遍历,遍历每个叶子节点,路径和满足条件则将该路径保存下来。  

    2024年02月11日
    浏览(34)
  • 力扣hot100 -- 双指针

    目录 🎂移动零 🌙盛最多水的容器 🌼三数之和 🌼接雨水 前缀和 + 辅助数组 双指针 单调栈 283. 移动零 - 力扣(LeetCode) 关于swap 思路 i = 0, j = 0 为了保证 0 都在末尾,且顺序不变 i 指向 0 j 指向 非0 元素时 交换两者(交换后,nums[x] = i 都是非0元素; i nums[x] = j,都是 0)

    2024年02月20日
    浏览(30)
  • 力扣hot100刷题记录

    二刷hot100,坚持每天打卡3道题!!! Today:2023-09-24

    2024年02月13日
    浏览(43)
  • 力扣HOT100 - 160. 相交链表

    解题思路:

    2024年04月12日
    浏览(48)
  • 力扣:113. 路径总和 II(Python3)

    给你二叉树的根节点  root  和一个整数目标和  targetSum  ,找出所有  从根节点到叶子节点  路径总和等于给定目标和的路径。 叶子节点  是指没有子节点的节点。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示例 1: 输入:root = [5,4,

    2024年02月07日
    浏览(42)
  • 力扣hot100 最长有效括号 动态规划

    Problem: 32. 最长有效括号 👨‍🏫 参考题解 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月20日
    浏览(77)
  • 力扣hot100 单词拆分 变形背包 排列

    Problem: 139. 单词拆分 👨‍🏫 参考题解 时间复杂度: O ( n 3 ) O(n^3) O ( n 3 )

    2024年01月20日
    浏览(43)
  • 力扣hot100 杨辉三角 递归 DP

    Problem: 118. 杨辉三角 👨‍🏫 参考地址 时间复杂度: 添加时间复杂度, 示例: O ( n ) O(n) O ( n ) 空间复杂度: 添加空间复杂度, 示例: O ( n ) O(n) O ( n )

    2024年01月17日
    浏览(39)
  • 力扣hot100 颜色分类 双指针 滚动赋值

    Problem: 75. 颜色分类 描述你的解题方法 时间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( 1 ) O(1) O ( 1 ) 👨‍🏫 参考题解

    2024年01月18日
    浏览(40)
  • 力扣hot100 排序链表 归并排序 递归

    Problem: 148. 排序链表 👩‍🏫 参考 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月25日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包