leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2385.cpp (1510B)

      1 class Solution {
      2   public:
      3     int amountOfTime(TreeNode *root, int start) const {
      4         unordered_map<TreeNode *, TreeNode *> parent;
      5         queue<TreeNode *> q;
      6         TreeNode *infected;
      7 
      8         q.push(root);
      9         while (!q.empty()) {
     10             TreeNode *root = q.front();
     11             q.pop();
     12             if (root->val == start) {
     13                 infected = root;
     14                 break;
     15             }
     16 
     17             if (root->left) {
     18                 parent.insert({root->left, root});
     19                 q.push(root->left);
     20             }
     21 
     22             if (root->right) {
     23                 parent.insert({root->right, root});
     24                 q.push(root->right);
     25             }
     26         }
     27 
     28         int depth = -1;
     29         q = queue<TreeNode *>();
     30         q.push(infected);
     31         while (!q.empty()) {
     32             depth++;
     33             for (int k = q.size(); k > 0; k--) {
     34                 TreeNode *root = q.front();
     35                 q.pop();
     36                 if (parent.count(root)) {
     37                     TreeNode *prnt = parent[root];
     38                     (prnt->left == root ? prnt->left : prnt->right) = nullptr;
     39                     q.push(parent[root]);
     40                 }
     41                 if (root->left) {
     42                     q.push(root->left);
     43                     parent.erase(root->left);
     44                 }
     45                 if (root->right) {
     46                     q.push(root->right);
     47                     parent.erase(root->right);
     48                 }
     49             }
     50         }
     51         return depth;
     52     }
     53 };