Grokking 205

class Solution {

  public class TreeNode {
    int val;
   TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
  }

  Map<Integer, List<Integer>> graph;

  public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    // setup
    this.graph = new HashMap<>();

    // do dfs to build graph
    dfs(root, null);

    // do bfs to find distance k node
    Set<Integer> visited = new HashSet<>();

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(target.val);
    visited.add(target.val);

    List<Integer> ans = new LinkedList<>();

    int dist = 0;
    while (!queue.isEmpty()) {
      int qSize = queue.size();

      // dist == k, build answer
      if (dist == k) {
        while (!queue.isEmpty()) {
          ans.add(queue.poll());
        }

        break;
      }

      for (int i = 0; i < qSize; i++) {
        int at = queue.poll();

        for (Integer to : graph.get(at)) {
          if (!visited.contains(to)) {
            queue.offer(to);
            visited.add(to);
          }
        }
      }

      dist++;
    }

    return ans;
  }

  void dfs(TreeNode root, TreeNode parent) {

    if (root == null) {
      return;
    }

    graph.putIfAbsent(root.val, new LinkedList<Integer>());

    if (parent != null) {
      graph.putIfAbsent(parent.val, new LinkedList<Integer>());

      graph.get(root.val).add(parent.val);
      graph.get(parent.val).add(root.val);
    }

    dfs(root.left, root);
    dfs(root.right, root);
  }

}