Date_Structures/amountOfTimeForBinaryTreeToBeAffected.cpp at main · Arpit-Verma-2003/Date_Structures · GitHub

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
65
66
67
68
69
70
71
72
73
74
75
76
/**
 * 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:

    TreeNode* setParent(TreeNode* root,map<TreeNode*,TreeNode*>&mp,int target){
        // base case
        if(!root) return NULL;
        TreeNode* res = NULL;
        queue<TreeNode*> q;
        q.push(root);
        mp[root] = NULL;
        while(!q.empty()){
            TreeNode* front = q.front();
            q.pop();
            if(front->val==target) res = front;
            if(front->left){
                q.push(front->left);
                mp[front->left] = front;
            }
            if(front->right) {
                q.push(front->right);
                mp[front->right] = front;
            }
        }
        return res;
    }

    int countTime(TreeNode* root,map<TreeNode*,TreeNode*>&mp){
        map<TreeNode*,bool> vis;
        queue<TreeNode*>q;
        q.push(root);
        vis[root] = true;
        int ans = 0;
        while(!q.empty()){
            bool flag = 0;
            int qsize = q.size();
            for(int i=0;i<qsize;i++){
                TreeNode* front = q.front();
                q.pop();
                if(front->left&&!vis[front->left]){
                    flag = 1;
                    vis[front->left] = true;
                    q.push(front->left);
                }
                if(front->right&&!vis[front->right]){
                    flag = 1;
                    vis[front->right] = true;
                    q.push(front->right);
                }
                if(mp[front]&&!vis[mp[front]]){
                    flag = 1;
                    vis[mp[front]] = true;
                    q.push(mp[front]);
                }
            }
            if(flag == 1) ans++;
        }
        return ans;
    }

    int amountOfTime(TreeNode* root, int target) {
        map<TreeNode*,TreeNode*>mp;
        TreeNode* node = setParent(root,mp,target);
        return countTime(node,mp);
    }
};