863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

image.png

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

输出：[7,4,1]

思路：构建parent结点，bfs遍历K次，返回queue中的值。
思路2： 构建HashMap<TreeNode,depth>。 找到该cur与target的最近公共祖先，判断depth(target)+depth(cur) = K-2*depth(parent);

class Solution {
    Map<TreeNode, TreeNode> parent;
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        parent = new HashMap();
        dfs(root, null);
        Queue<TreeNode> queue = new LinkedList();
        queue.add(target);
        Set<TreeNode> seen = new HashSet();
        seen.add(target);
        List<Integer> res = new ArrayList();
        int step = 0;
        while(!queue.isEmpty()){
            if(step==K){
                while(!queue.isEmpty()){
                    res.add(queue.poll().val);
                }
                return res;
            }
            int size = queue.size();
            while(size -->0){
                TreeNode cur = queue.poll();
                if(cur.left!=null&&!seen.contains(cur.left)){
                    seen.add(cur.left);
                    queue.add(cur.left);
                }
                if(cur.right!=null&&!seen.contains(cur.right)){
                    seen.add(cur.right);
                    queue.add(cur.right);
                }
                if(parent.get(cur)!=null&&!seen.contains(parent.get(cur))){
                    seen.add(parent.get(cur));
                    queue.add(parent.get(cur));
                }
            }
            step++;
        }
        return res;
    }

    public void dfs(TreeNode node, TreeNode par) {
        if (node != null) {
            parent.put(node, par);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }
}