[每日一题] 2385.感染二叉树需要的总时间

博主： Richard
发布时间：2024 年 04 月 24 日
101 次浏览
暂无评论
3602字数
分类： LeetCode

> https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/description/?envType=daily-question&envId=2024-04-11

题目要求 $start$ 节点到其他节点最大的距离，很容易想到使用广搜来找。但 $start$ 节点不一定是根节点，所以可以使用 DFS 将二叉树解析成无向图，再用 BFS 进行搜索：

```c++
/**
 * 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:
    int amountOfTime(TreeNode* root, int start) {
        std::unordered_map<int, std::vector<int>> graph;
        std::unordered_set<int> visited;

std::function<void(TreeNode *)> dfs = [&](TreeNode *node) {
            for (TreeNode *child : std::vector<TreeNode *>{node->left, node->right}) {
                if (child != nullptr) {
                    graph[node->val].push_back(child->val);
                    graph[child->val].push_back(node->val);
                    dfs(child);
                }
            }
        };

auto bfs = [&start, &graph, &visited] () {
            std::queue<int> nodes, depth;
            nodes.push(start);
            depth.push(0);

int curNode, curDepth, maxDepth = 0;
            while(!nodes.empty()) {
                curNode = nodes.front();
                curDepth = depth.front();
                nodes.pop();
                depth.pop();
                
                if (visited.find(curNode) != visited.end())
                    continue;
                else 
                    visited.insert(curNode);

if (curDepth > maxDepth)
                    maxDepth = curDepth;

for (const auto &next : graph[curNode]) {
                    nodes.push(next);
                    depth.push(curDepth + 1);
                }
            }

return maxDepth;
        };

dfs(root);
        return bfs();
    }
};
```

- 时间复杂度 $O(n)$ ，其中 $n$ 为树中节点数。
- 空间复杂度 $O(n)$ 。

这么做的话虽然时间复杂度是 $O(n)$ ，但还是遍历了多次所有节点。能不能在一次遍历中找出需要的答案呢？

每个节点会有三种情况：

1. 子树中不含初始感染节点；
2. 子树中含有初始感染节点；
3. 该节点为初始感染节点；

对于情况 1 ，说明感染节点在其祖先节点或者另一棵树内，所以直接返回该子树最大的深度即可。

对于情况 2 ，需要判断一下初始感染节点到该节点另一个子树的距离是否为最大值，然后返回初始感染节点到该节点的距离。参考之前并查集的空间优化方法，这个距离可以通过负数来表示。

对于情况 3 ，直接判断该节点的子树深度是否为最大值，然后返回 -1 。

最后通过 DFS 遍历整棵树，即可得到答案：

```c++
/**
 * 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:
    int amountOfTime(TreeNode* root, int start) {
        int res = 0;
        std::function<int(TreeNode* &)> dfs = [&](TreeNode* &node) {
            if (node == nullptr)
                return 0;

int leftTree = dfs(node->left), rightTree = dfs(node->right);

if (node->val == start) {
                res = std::max(leftTree, rightTree);
                return -1;
            }

if (leftTree >= 0 && rightTree >= 0)
                return std::max(leftTree, rightTree) + 1;

res = std::max(res, abs(leftTree - rightTree));
            return std::min(leftTree, rightTree) - 1;
        };

dfs(root);
        return res;
    }
};
```

- 时间复杂度 $O(n)$ ，其中 $n$ 为树中节点数。
- 空间复杂度 $O(n)$ 。

最后修改：2024 年 05 月 06 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

[每日一题] 216.组合总和III - Richardの小小杂货铺
[...]};时间复杂度 $O(M \times 2^M)$ ...
fa
最新的版本无法登陆，能否指导一下。多谢
rantrism
您好～我是腾讯云开发者社区运营，关注了您分享的技术文章，觉得内...
examine
Richard什么时候带我
https://telegra.ph/Technology-A-linchpin-To-Maintain-Businesses-Handle-Remote-Workforce-Amid-Pandemic---Technology-02-16
You actually expressed this ade...

[每日一题] 2385.感染二叉树需要的总时间

Richard • 2024 年 04 月 24 日

> https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/description/?envType=daily-question&envId=2024-04-11

auto bfs = [&start, &graph, &visited] () {
            std::queue<int> nodes, depth;
            nodes.push(start);
            depth.push(0);

if (curDepth > maxDepth)
                    maxDepth = curDepth;

for (const auto &next : graph[curNode]) {
                    nodes.push(next);
                    depth.push(curDepth + 1);
                }
            }

return maxDepth;
        };

dfs(root);
        return bfs();
    }
};
```

- 时间复杂度 $O(n)$ ，其中 $n$ 为树中节点数。
- 空间复杂度 $O(n)$ 。

这么做的话虽然时间复杂度是 $O(n)$ ，但还是遍历了多次所有节点。能不能在一次遍历中找出需要的答案呢？

每个节点会有三种情况：

1. 子树中不含初始感染节点；
2. 子树中含有初始感染节点；
3. 该节点为初始感染节点；

对于情况 1 ，说明感染节点在其祖先节点或者另一棵树内，所以直接返回该子树最大的深度即可。

对于情况 3 ，直接判断该节点的子树深度是否为最大值，然后返回 -1 。

最后通过 DFS 遍历整棵树，即可得到答案：

```c++
/**
 * 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:
    int amountOfTime(TreeNode* root, int start) {
        int res = 0;
        std::function<int(TreeNode* &)> dfs = [&](TreeNode* &node) {
            if (node == nullptr)
                return 0;

int leftTree = dfs(node->left), rightTree = dfs(node->right);

if (node->val == start) {
                res = std::max(leftTree, rightTree);
                return -1;
            }

if (leftTree >= 0 && rightTree >= 0)
                return std::max(leftTree, rightTree) + 1;

res = std::max(res, abs(leftTree - rightTree));
            return std::min(leftTree, rightTree) - 1;
        };

dfs(root);
        return res;
    }
};
```

- 时间复杂度 $O(n)$ ，其中 $n$ 为树中节点数。
- 空间复杂度 $O(n)$ 。

[每日一题] 2385.感染二叉树需要的总时间

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【转】提问的智慧

【枫燃异闻录】利用python爬取Bangumi评分

BUUCTF-web writeup (更新中)

Typecho附件上传大小限制修改

记录一道卡了我好几天的题目

[每日一题] 2079.给植物浇水

[转] 搭建KMS服务器

RC4加密算法学习记录

实验2 数据表示实验

[每日一题] 521.最长特殊序列Ⅰ

[每日一题] 2385.感染二叉树需要的总时间

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

[每日一题] 2385.感染二叉树需要的总时间

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款