leetcode2389--感染二叉树需要的总时间

2024-04-26 02:52

本文主要是介绍leetcode2389--感染二叉树需要的总时间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 题意

给定一个节点,每秒该节点会感染相邻的节点,受感染的节点下一秒也会感染周围节点;

求使得所有节点感染的时间

2. 题解

2.1 dfs建图+bfs搜索层次

我们将目标节点找到,并从该节点出发找到以该节点形成的树的深度即可。

  • 我的代码
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {public:// * transform tree to graph// * sparse graphvoid build_graph(TreeNode * root, vector<vector<int>> &g) {if (nullptr == root)return;if ( root->left) {g[root->val].push_back( root->left->val);g[root->left->val].push_back(root->val);build_graph(root->left, g);}if ( root->right ) {g[root->val].push_back(root->right->val);g[root->right->val].push_back(root->val);build_graph(root->right, g);}}int amountOfTime(TreeNode* root, int start) {const int MAXN = 1e5 + 1;vector<vector<int>> g(MAXN, vector<int>());build_graph(root, g);int ans = 0;int last = start;queue<int> q;q.push(start);vector<int> vis(MAXN, 0);while (!q.empty()) {int cur = q.front();q.pop();vis[cur] = 1;for (int v:g[cur])if (!vis[v])q.push(v);if (cur == last) {ans++;last = q.back();}}return ans - 1;}
};

2.2 dfs建图+dfs求深度

我们需要找到每个节点的父节点,并且用一个from来表示当前节点是从哪来的以避免重复遍历。

  • 我的代码
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {public:// * transform tree to graph// * sparse graphvoid get_fa(unordered_map<int,TreeNode *> &fa, TreeNode *root, int start, TreeNode *&start_node) {if (root == nullptr)return;if ( root->left)fa[root->left->val] = root;if ( root->right)fa[root->right->val] = root;if ( root->val == start)start_node = root;get_fa(fa, root->left, start, start_node );get_fa(fa, root->right, start, start_node );}int getDepth(TreeNode *root, int from,const unordered_map<int,TreeNode*> &fa) {if ( nullptr == root)return -1;int llen = -1;int rlen = -1;int flen = -1;if ( root->left && root->left->val != from)llen = getDepth(root->left, root->val, fa);if ( root->right && root->right->val != from )rlen = getDepth( root->right, root->val, fa);if (fa.find(root->val) != fa.end() &&fa.at(root->val)->val != from) {// cout << "fa-" << fa.at(root->val)->val << endl;flen = getDepth( fa.at(root->val), root->val, fa);}int ans = max(llen, rlen);ans = max(flen, ans);return ans + 1;}int amountOfTime(TreeNode* root, int start) {unordered_map<int,TreeNode *> fa;TreeNode *start_node;get_fa( fa, root, start, start_node);return  getDepth(start_node, -1, fa);}
};
  • 03xf题解

TreeNode* fa[100001]; // 哈希表会超时,改用数组class Solution {int start;TreeNode* start_node;void dfs(TreeNode* node, TreeNode* from) {if (node == nullptr) {return;}fa[node->val] = from; // 记录每个节点的父节点if (node->val == start) {start_node = node; // 找到 start}dfs(node->left, node);dfs(node->right, node);}int maxDepth(TreeNode* node, TreeNode* from) {if (node == nullptr) {return -1; // 注意这里是 -1,因为 start 的深度为 0}int res = -1;if (node->left != from) {res = max(res, maxDepth(node->left, node));}if (node->right != from) {res = max(res, maxDepth(node->right, node));}if (fa[node->val] != from) {res = max(res, maxDepth(fa[node->val], node));}return res + 1;}public:int amountOfTime(TreeNode* root, int start) {this->start = start;dfs(root, nullptr);return maxDepth(start_node, start_node);}
};作者:灵茶山艾府
链接:https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solutions/2753470/cong-liang-ci-bian-li-dao-yi-ci-bian-li-tmt0x/comments/2287846/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
2.3 一次遍历
  • 03xf
class Solution {int ans = 0, start;pair<int, bool> dfs(TreeNode* node) {if (node == nullptr) {return {0, false};}auto [l_len, l_found] = dfs(node->left);auto [r_len, r_found] = dfs(node->right);if (node->val == start) {// 计算子树 start 的最大深度// 注意这里和方法一的区别,max 后面没有 +1,所以算出的也是最大深度ans = max(l_len, r_len);return {1, true}; // 找到了 start}if (l_found || r_found) {// 只有在左子树或右子树包含 start 时,才能更新答案ans = max(ans, l_len + r_len); // 两条链拼成直径// 保证 start 是直径端点return {(l_found ? l_len : r_len) + 1, true};}return {max(l_len, r_len) + 1, false};}public:int amountOfTime(TreeNode* root, int start) {this->start = start;dfs(root);return ans;}
};作者:灵茶山艾府
链接:https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solutions/2753470/cong-liang-ci-bian-li-dao-yi-ci-bian-li-tmt0x/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这篇关于leetcode2389--感染二叉树需要的总时间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/936523

相关文章

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Feign Client超时时间设置不生效的解决方法

《FeignClient超时时间设置不生效的解决方法》这篇文章主要为大家详细介绍了FeignClient超时时间设置不生效的原因与解决方法,具有一定的的参考价值,希望对大家有一定的帮助... 在使用Feign Client时,可以通过两种方式来设置超时时间:1.针对整个Feign Client设置超时时间

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python如何获取域名的SSL证书信息和到期时间

《Python如何获取域名的SSL证书信息和到期时间》在当今互联网时代,SSL证书的重要性不言而喻,它不仅为用户提供了安全的连接,还能提高网站的搜索引擎排名,那我们怎么才能通过Python获取域名的S... 目录了解SSL证书的基本概念使用python库来抓取SSL证书信息安装必要的库编写获取SSL证书信息

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

如何利用Java获取当天的开始和结束时间

《如何利用Java获取当天的开始和结束时间》:本文主要介绍如何使用Java8的LocalDate和LocalDateTime类获取指定日期的开始和结束时间,展示了如何通过这些类进行日期和时间的处... 目录前言1. Java日期时间API概述2. 获取当天的开始和结束时间代码解析运行结果3. 总结前言在J