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实现时间与字符串互相转换详解

《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

修改若依框架Token的过期时间问题

《修改若依框架Token的过期时间问题》本文介绍了如何修改若依框架中Token的过期时间,通过修改`application.yml`文件中的配置来实现,默认单位为分钟,希望此经验对大家有所帮助,也欢迎... 目录修改若依框架Token的过期时间修改Token的过期时间关闭Token的过期时js间总结修改若依

Go Mongox轻松实现MongoDB的时间字段自动填充

《GoMongox轻松实现MongoDB的时间字段自动填充》这篇文章主要为大家详细介绍了Go语言如何使用mongox库,在插入和更新数据时自动填充时间字段,从而提升开发效率并减少重复代码,需要的可以... 目录前言时间字段填充规则Mongox 的安装使用 Mongox 进行插入操作使用 Mongox 进行更

对postgresql日期和时间的比较

《对postgresql日期和时间的比较》文章介绍了在数据库中处理日期和时间类型时的一些注意事项,包括如何将字符串转换为日期或时间类型,以及在比较时自动转换的情况,作者建议在使用数据库时,根据具体情况... 目录PostgreSQL日期和时间比较DB里保存到时分秒,需要和年月日比较db里存储date或者ti

Python 标准库time时间的访问和转换问题小结

《Python标准库time时间的访问和转换问题小结》time模块为Python提供了处理时间和日期的多种功能,适用于多种与时间相关的场景,包括获取当前时间、格式化时间、暂停程序执行、计算程序运行时... 目录模块介绍使用场景主要类主要函数 - time()- sleep()- localtime()- g