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 graph
void 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 graph
void 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
