863. All Nodes Distance K in Binary Tree

Problem:

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.

Analysis:
这道题和之前那道742. Closest Leaf in a Binary Tree 类似。都是先建图然后BFS。不同点在于，这道题如果按742的图的构建方式，test case [1] 通过不了， 因为node 1根本不会出现在图中。就会出现null pointer错误。

另外一个点就是，在while循环一开始判断k的值，循环底部k--。如果反过来而且k==0, 就得不到结果。

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> distanceK(TreeNode root, TreeNode target, int K) { Map<TreeNode, List<TreeNode>> graph = new HashMap<>(); List<Integer> res = new ArrayList<>(); if (root == null) return res; buildGraph(root, null, graph); Queue<TreeNode> queue = new LinkedList<>(); Set<TreeNode> visited = new HashSet<>(); queue.offer(target); visited.add(target); while (!queue.isEmpty()) { int size = queue.size(); if (K == 0) { break; } for (int i =0; i < size; i++){ TreeNode cur = queue.poll(); for (TreeNode node: graph.get(cur)) { if (visited.add(node)) { queue.offer(node); } } } K--; } while (!queue.isEmpty()) { res.add(queue.poll().val); } return res; } private void buildGraph(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> graph) { if (node == null) return; if (!graph.containsKey(node)) { graph.put(node, new ArrayList<TreeNode>()); if (parent != null) { graph.get(node).add(parent); graph.get(parent).add(node) ; } buildGraph(node.left, node, graph); buildGraph(node.right, node, graph); } } }