Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 10

Description

Amount of Time for Binary Tree to Be Infected

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:

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:

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, 105].
• 1 <= Node.val <= 105
• Each node has a unique value.
• A node with a value of start exists in the tree.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  void add(TreeNode *root, map<int, vector<int>> &edges) {
    if(root->left) {
      edges[root->val].push_back(root->left->val);
      edges[root->left->val].push_back(root->val);
      add(root->left, edges);
    }
    if(root->right) {
      edges[root->val].push_back(root->right->val);
      edges[root->right->val].push_back(root->val);
      add(root->right, edges);
    }
  }
public:
  int amountOfTime(TreeNode* root, int start) {
    map<int, vector<int>> edges;
    add(root, edges);

    int time = -1;
    queue<pair<int, int>> q;
    q.push({-1, start});
    while(q.size()) {
      int sz = q.size();
      for(auto _ = 0; _ < sz; ++_) {
        auto [parent, current] = q.front();
        q.pop();
        for(auto next : edges[current]) {
          if(next == parent) continue;
          q.push({current, next});
        }
      }
      time += 1;
    }
    return time;
  }
};

// Accepted
// 80/80 cases passed (569 ms)
// Your runtime beats 21.97 % of cpp submissions
// Your memory usage beats 36.64 % of cpp submissions (165 MB)