Given aundirected graph, anodeand atarget, return the nearest node to given node which value of it is target, returnNULLif you can't find.

There is amappingstore the nodes' values in the given parameters.

Notice

It's guaranteed there is only one available solution

Have you met this question in a real interview?

Yes

Example

2------3  5
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      1 --4
Give a node 1, target is 50

there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50

Return node 4

代码未验证

    class UndirectedGraphNode
    {
       public int label;
       public List<UndirectedGraphNode> neighbors;
        public UndirectedGraphNode (int x){
            label = x;
            neighbors = new List<UndirectedGraphNode>();
      }
    };
    class Program
    {
        public UndirectedGraphNode searchNode(List<UndirectedGraphNode> graph,
                                              IDictionary<UndirectedGraphNode, int?> values,
                                               UndirectedGraphNode node, int target)
        {
            Queue<UndirectedGraphNode> queue = new Queue<UndirectedGraphNode>();
            HashSet<UndirectedGraphNode> hash = new HashSet<UndirectedGraphNode>();
            queue.Enqueue(node);
            hash.Add(node);

            while (hash.Count > 0) {
                UndirectedGraphNode head = queue.Dequeue();
                if (values[head] == target) {
                    return head;
                }
                foreach (UndirectedGraphNode n in head.neighbors)
                {
                    if (!hash.Contains(n))
                    {
                        queue.Enqueue(n);
                        hash.Add(n);
                    }
                }
            }


            return null;
        }