All Nodes Distance K in Binary Tree - Post #200!

From Leetcode, problem #863: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node.  The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.



Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

1. The given tree is non-empty.
2. Each node in the tree has unique values 0 <= node.val <= 500.
3. The target node is a node in the tree.
4. 0 <= K <= 1000.

Here is the idea (ignoring the special cases of zero or one node in the tree, which are boring to code, but trivial):

• Flatten up the tree into a hashtable. The hashtable contains every node as a key and a list of nodes it touches in the tree as the value. For example: Hash(5) = List(3,6,2)
• The above operation is done in linear time, linear space
• Now, given a target node recursively traverse the hashtable, decreasing K as you go along, and when K reaches 0 you found a node with distance (original) K
• Need to take care of the nodes already visited (remember that you have transformed the tree into an non-directed graph)

Not super fast, but does the job. This is my post #200! (Not 200 factorial!). Cheers, Marcelo

public class Solution
{
 private Hashtable treeMap = new Hashtable();
 public IList DistanceK(TreeNode root, TreeNode target, int K)
 {
  List retVal = new List();

  //Special case: one or zero nodes
  if (root == null) return retVal;
  if (root.left == null && root.right == null && target.val == root.val)
  {
   if (K == 0)
   {
    retVal.Add(target.val);
   }
   return retVal;
  }

  //All cases
  BuildTreeMap(null, root);
  Hashtable used = new Hashtable();
  used.Add(target.val, true);
  DistanceK(target.val, K, used, retVal);
  return retVal;
 }

 private void DistanceK(int target, int K, Hashtable used, IList retVal)
 {
  if (K == 0)
  {
   retVal.Add(target);
   return;
  }

  LinkedList neighbors = (LinkedList)treeMap[target];
  foreach (int n in neighbors)
  {
   if (!used.ContainsKey(n))
   {
    used.Add(n, true);
    DistanceK(n, K - 1, used, retVal);
   }
  }
 }

 private void BuildTreeMap(TreeNode parent, TreeNode child)
 {
  if (child == null) return;
  if (parent != null)
  {
   LinkedList list = null;
   if (!treeMap.ContainsKey(parent.val))
   {
    list = new LinkedList();
    list.AddLast(child.val);
    treeMap.Add(parent.val, list);
   }
   else
   {
    list = (LinkedList)treeMap[parent.val];
    list.AddLast(child.val);
   }
   if (!treeMap.ContainsKey(child.val))
   {
    list = new LinkedList();
    list.AddLast(parent.val);
    treeMap.Add(child.val, list);
   }
   else
   {
    list = (LinkedList)treeMap[child.val];
    list.AddLast(parent.val);
   }
  }
  BuildTreeMap(child, child.left);
  BuildTreeMap(child, child.right);
 }
}