854. Closest Leaf in a Binary Tree

Code(Language:C++)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

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*, TreeNode*> parent; 
    TreeNode * search(TreeNode* root, int k){
        if(root == NULL){
            return NULL; 
        }
        TreeNode *res = root; 
        if(root->left){
            parent[root->left] = root; 
            TreeNode *tmp = search(root->left, k);//这里的目的是遍历完真个tree，不是找到k就结束了             if(tmp->val == k){
                res = tmp; 
            }
        }
        if(root->right){
            parent[root->right] = root; 
            TreeNode *tmp = search(root->right, k); 
            if(tmp->val == k){
                res = tmp; 
            }
        }
        return res; 
    }
    
    int findClosestLeaf(TreeNode * root, int k) {
        // Write your code here
        // DQ search k and build parents relation 
        // BFS search colset leaf. 
        TreeNode *start = search(root, k); 
        std::queue<TreeNode *> q;
        q.push(start); 
        unordered_set<TreeNode *> visited; 
        visited.insert(start);
        while(!q.empty()){
            TreeNode *tmp = q.front();
            q.pop();
            if(tmp->left == NULL && tmp->right == NULL){
                return tmp->val; 
            }
            // left substr
            if(tmp->left != NULL && visited.count(tmp->left) == 0){
                q.push(tmp->left); 
                visited.insert(tmp->left); 
            }
            if(tmp->right != NULL && visited.count(tmp->right) == 0){
                q.push(tmp->right);
                visited.insert(tmp->right); 
            }
            if(parent.count(tmp) && visited.count(parent[tmp]) == 0){
                q.push(parent[tmp]);
                visited.insert(parent[tmp]); 
            }
        }
        return 0;
    }
};