2385. Amount of Time for Binary Tree to Be Infected

Posted on Edited on In

2385. Amount of Time for Binary Tree to Be Infected

Description

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Each minute, a node becomes infected if:

  • The node is currently uninfected.
  • The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

Example 1:

1
2
3
4
5
6
7
8
9
Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.

Example 2:

1
2
3
Input: root = [1], start = 1
Output: 0
Explanation: At minute 0, the only node in the tree is infected so we return 0.

Constraints:

  • The number of nodes in the tree is in the range [1, 10^5].
  • 1 <= Node.val <= 10^5
  • Each node has a unique value.
  • A node with a value of start exists in the tree.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * 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:
    unordered_map<TreeNode*, TreeNode*> parent;
    unordered_set<int> visited;
    TreeNode* node;

    int amountOfTime(TreeNode* root, int start) {
        traverse(root, start);
        queue<TreeNode*> q;
        q.push(node);
        visited.insert(start);
        int time = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* curNode = q.front();
                q.pop();
                if (curNode->left && !visited.contains(curNode->left->val)) {
                    visited.insert(curNode->left->val);
                    q.push(curNode->left);
                }
                if (curNode->right && !visited.contains(curNode->right->val)) {
                    visited.insert(curNode->right->val);
                    q.push(curNode->right);
                }
                if (parent.contains(curNode) && !visited.contains(parent[curNode]->val)) {
                    visited.insert(parent[curNode]->val);
                    q.push(parent[curNode]);
                }
            }
            if (q.empty()) return time;
            time++;
        }
        return time;
    }

    void traverse(TreeNode* root, int start) {
        if (!root) {
            return;
        }
        if (root->val == start) {
            node = root;
        }
        if (root->left) {
            parent[root->left] = root;
        }
        if (root->right) {
            parent[root->right] = root;
        }
        traverse(root->left, start);
        traverse(root->right, start);
    }
};