描述

给定一张无向图，一个结点以及一个目标值，返回距离这个结点最近且值为目标值的结点，如果不能找到则返回 NULL。
在给出的参数中, 我们用 map 来存结点的值

注意事项

保证答案唯一

样例

    2------3  5
     \     |  | 
      \    |  |
       \   |  |
        \  |  |
        1 --4

给出 节点1，目标值为 50
有个哈希表的值为[3,4,10,50,50]，表示:

    节点1的值为3
    节点2的值为4
    节点3的值为10
    节点4的值为50
    节点5的值为50

返回 节点4
实际上考的就是BFS模板，如果只存在一个最近点用下列代码即可，若存在几个则需分层，参考之前二叉树分层

代码

/**
 * Definition for graph node.
 * class GraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *         label = x; neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */
public class Solution {
    /**
     * @param graph a list of Undirected graph node
     * @param values a hash mapping, <UndirectedGraphNode, (int)value>
     * @param node an Undirected graph node
     * @param target an integer
     * @return the a node
     */
    public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                          Map<UndirectedGraphNode, Integer> values,
                                          UndirectedGraphNode node,
                                          int target) {
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        Set<UndirectedGraphNode> hash = new HashSet<UndirectedGraphNode>();

        queue.offer(node);
        hash.add(node);

        while (!queue.isEmpty()) {
            UndirectedGraphNode head = queue.poll();
            // 对图用队列做BFS，碰到的第一个点一定是最近的目标点？
            if (values.get(head) == target) {
                return head;
            }
            for (UndirectedGraphNode nei : head.neighbors) {
                if (!hash.contains(nei)){
                    queue.offer(nei);
                    hash.add(nei);
                }
            }
        }
        return null;
    }
}

本题典型的的BST求最短路径问题，值得注意的是结点值用哈希方式存储，注意调用方法(values.get(head))不是head.vals