共计 1473 个字符，预计需要花费 4 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给定一个二叉树（具有根结点 root），一个目标结点 target，和一个整数值 K。
返回到目标结点 target 距离为 K 的所有结点的值的列表。答案可以以任何顺序返回。
解答：这一题显然是利用广度优先搜索来探测距离，然而树是一个有向图，我们需要一个无向图来进行广度优先搜索。因此，先把树变成一个无向图，然后广度优先搜索这个无向图。距离不断增加，就可以找到每个节点和目标节点的距离。java ac 代码：
/**
* 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) {
List<Integer> ans = new ArrayList(1000);
HashMap<TreeNode,List<TreeNode>>map = new HashMap(1<<10);
dfs1(root,map);
dfs2(root,map);
ArrayDeque<TreeNode> deque = new ArrayDeque(100);
HashSet<TreeNode>set = new HashSet(1<<10);
HashMap<TreeNode,Integer> map2 = new HashMap(1<<10);
set.add(target);
deque.offer(target);
map2.put(target,0);
while(!deque.isEmpty())
{
TreeNode temp = deque.poll();
int num = map2.get(temp)+1;
for(TreeNode node:map.get(temp))
if(!set.contains(node))
{
set.add(node);
deque.offer(node);
map2.put(node,num);
}
}
for(Map.Entry<TreeNode,Integer> entry:map2.entrySet())
if(entry.getValue() == K)ans.add(entry.getKey().val);
return ans;
}
void dfs1(TreeNode root,HashMap<TreeNode,List<TreeNode>>map)
{
if(root == null)return;
map.put(root,new ArrayList(100));
dfs1(root.left,map);
dfs1(root.right,map);
}
void dfs2(TreeNode root,HashMap<TreeNode,List<TreeNode>>map)
{
if(root == null)return;
if(root.left != null)
{
map.get(root).add(root.left);
map.get(root.left).add(root);
}
if(root.right != null)
{
map.get(root).add(root.right);
map.get(root.right).add(root);
}
dfs2(root.left,map);
dfs2(root.right,map);
}
}
