力扣(LeetCode)863

题目地址：

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);
        
    }
    
}