Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.9 kB
0
Indexable
Never

class Solution {
    
    Node *targetPtr = NULL;
    
  public:
    int minTime(Node* root, int target) 
    {
        unordered_map<Node*, Node*> parentMap;
        
        parentMap.insert({root, NULL});
        buildParentMap(root, parentMap, target);
        
        queue<Node*> q;
        set<Node*> st;
        
        int timer = -1;
        
        q.push(targetPtr);
        st.insert(targetPtr);
        
        while(!q.empty()) {
            int qLen = q.size();
            timer++;
            
            for (int i = 1; i <= qLen; i++) {
                Node* curr = q.front();
                q.pop();
                
                Node *parent = parentMap[curr];
                Node *left = curr -> left;
                Node *right = curr -> right;
                
                if (parent != NULL && st.find(parent) == st.end()) {
                    st.insert(parent);
                    q.push(parent);
                }
                
                if (left != NULL && st.find(left) == st.end()) {
                    st.insert(left);
                    q.push(left);
                }
                
                if (right != NULL && st.find(right) == st.end()) {
                    st.insert(right);
                    q.push(right);
                }
            }
        }
        
        return timer;
    }
    
    void buildParentMap(Node* root, unordered_map<Node*, Node*> &parentMap, int target) {
        if (root == NULL)
            return;
            
        if (root -> data == target)
            targetPtr = root;
            
        if (root -> left != NULL)
            parentMap.insert({root -> left, root});
            
        if (root -> right != NULL)
            parentMap.insert({root -> right, root});
        
        buildParentMap(root -> left, parentMap, target);
        buildParentMap(root -> right, parentMap, target);
    }
    
};