Untitled
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); } };