LeetCode 742. 二叉树最近的叶节点（建立父节点信息+BFS）

示例 1：
输入：
root = [1, 3, 2], k = 1
二叉树图示：
          1
         / \
        3   2

输出： 2 (或 3)
解释： 2 和 3 都是距离目标 1 最近的叶节点。
 
示例 2：
输入：
root = [1], k = 1
输出：1
解释： 最近的叶节点是根结点自身。
 
示例 3：
输入：
root = [1,2,3,4,null,null,null,5,null,6], k = 2
二叉树图示：
             1
            / \
           2   3
          /
         4
        /
       5
      /
     6

输出：3
解释： 值为 3（而不是值为 6）的叶节点是距离结点 2 的最近结点。
 
注：
root 表示的二叉树最少有 1 个结点且最多有 1000 个结点。
每个结点都有一个唯一的 node.val ，范围为 [1, 1000]。
给定的二叉树中有某个结点使得 node.val == k。

class Solution {
	unordered_map<TreeNode*,TreeNode*> father;
	queue<TreeNode*> q;
	unordered_set<TreeNode*> visited;
public:
    int findClosestLeaf(TreeNode* root, int k) {
    	father[root] = NULL;
    	dfs(root, k);
    	int size;
    	TreeNode* cur;
    	while(!q.empty())
    	{
    		size = q.size();
    		while(size--)
    		{
    			cur = q.front();
    			q.pop();
    			if(!cur->left && !cur->right)
    				return cur->val;
    			if(cur->left && !visited.count(cur->left))
    			{
    				q.push(cur->left);
    				visited.insert(cur->left);
    			}
    			if(cur->right && !visited.count(cur->right))
    			{
    				q.push(cur->right);
    				visited.insert(cur->right);
    			}
    			if(father[cur] && !visited.count(father[cur]))
    			{
    				q.push(father[cur]);
    				visited.insert(father[cur]);
    			}
    		}
    	}
    	return -1;
    }
    void dfs(TreeNode* root, int k) 
    {
    	if(!root) return;
    	if(root->val == k)
    	{
    		q.push(root);
    		visited.insert(root);
    	}
    	if(root->left)
    		father[root->left] = root;
    	if(root->right)
    		father[root->right] = root;
    	dfs(root->left,k);
    	dfs(root->right,k);
    }
};