图论16（Leetcode863.二叉树中所有距离为K的结点）

答案：

/*** 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<Integer, int[]> map = new HashMap<>();int[] link = {-1,-1,-1};map.put(root.val,link);Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size()!=0){TreeNode cur = queue.poll();int[] link1 = new int[3];int[]temp = map.get(cur.val);//cur包含父节点的linklink1[0] = temp[0];link1[1] = -1;link1[2] = -1;int[] link2 = {cur.val,-1,-1};//记录left right的父节点if(cur.left!=null){TreeNode left = cur.left;link1[1] = left.val;map.put(left.val,link2);queue.add(left);}if(cur.right!=null){TreeNode right = cur.right;link1[2] = right.val;map.put(right.val,link2);queue.add(right);}map.put(cur.val,link1);}map.forEach((key, value) -> System.out.println("Key = " + key + ", Value = " + value[0] +" "+ value[1]+" "+ value[2]));List<Integer> res = new ArrayList<>();Queue<Integer> queue2 = new LinkedList<>();Set<Integer> set = new HashSet<>();queue2.add(target.val);set.add(target.val);int step = 0;while(queue2.size()!=0){if(step==k){while(queue2.size()!=0){res.add(queue2.poll());}break;}int len = queue2.size();for(int i=0;i<len;i++){int node = queue2.poll();int value[] = map.get(node);if(value[0]!=-1&&!set.contains(value[0])){queue2.add(value[0]);set.add(value[0]);}if(value[1]!=-1&&!set.contains(value[1])){queue2.add(value[1]);set.add(value[1]);}if(value[2]!=-1&&!set.contains(value[2])){queue2.add(value[2]);set.add(value[2]);}}step++;}return res;}
}