AM 854. Closest Leaf in a Binary Tree
class Solution {
public:
/**
* @param root: the root
* @param k: an integer
* @return: the value of the nearest leaf node to target k in the tree
*/
unordered_map<TreeNode*, vector<TreeNode*>> mp;
int findClosestLeaf(TreeNode * root, int k) {
// Write your code here
TreeNode *target;
buildGraph(root, NULL, target, k);
std::queue<TreeNode *> q;
unordered_set<TreeNode *>set;
q.push(target);
set.insert(target);
while(!q.empty()){
TreeNode *tmp = q.front();
q.pop();
if(tmp->left == NULL && tmp->right == NULL){
return tmp->val;
}
for(auto i : mp[tmp]){
if(i == NULL || set.count(i)){
continue;
}
set.insert(i);
q.push(i);
}
}
}
void buildGraph(TreeNode *root, TreeNode* pre, TreeNode* &target, int k){
if(root == NULL){
return;
}
if(root->val == k){
target = root;
}
mp[root].push_back(root->left);
mp[root].push_back(root->right);
mp[root].push_back(pre);
buildGraph(root->left, root, target, k);
buildGraph(root->right, root, target, k);
return;
}
};
Comments
Post a Comment