LeetCode刷题【863】二叉树中所有距离为K的结点

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

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1



注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。

提示：

1. 给定的树是非空的。
2. 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
3. 目标结点 target 是树上的结点。
4. 0 <= K <= 1000.

题解

二叉树结构借助新增的map，经过dfs存下父节点信息转成图结构，然后再以target节点向外扩散，记下距离k即可

//leetcode submit region begin(Prohibit modification and deletion)




import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

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


    Map<TreeNode, TreeNode> parentMap;

    private List<Integer> res = new ArrayList<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        parentMap = new HashMap<>();
        dfs(root, null);
        Queue<TreeNode> queue = new LinkedList<>();
        int distance = 0;
        queue.offer(target);
        int stepSize;
        Set<TreeNode> visited = new HashSet<>();
        //多加一个null进来，把没有父节点为null和子节点为null的判断条件都加进去
        visited.add(null);
        //target也加入，自身已经访问过
        visited.add(target);
        while (!queue.isEmpty()){
            //距离为0就是自身，所以，当从queue头部开始遍历的时候，distance是0
            if (distance==k){
                //存结果
                for (TreeNode node : queue) {
                    res.add(node.val);
                }
                //这边有个小坑，没注意被绕了好久，上面for循环不会从queue中poll，
                // 然后继续进入while循环，形成死循环
                return res;
            }else{
                distance ++;
                stepSize = queue.size();
                //继续走下一步，往queue里塞父，左，右3个结点
                for (int i = 0; i < stepSize; i++) {
                    TreeNode current = queue.poll();
                    if (!visited.contains(parentMap.get(current))){
                        queue.offer(parentMap.get(current));
                        visited.add(parentMap.get(current));
                    }
                    if (!visited.contains(current.left)){
                        queue.offer(current.left);
                        visited.add(current.left);
                    }
                    if (!visited.contains(current.right)){
                        queue.offer(current.right);
                        visited.add(current.right);
                    }
                }
            }

        }
        return res;
    }


}
//leetcode submit region end(Prohibit modification and deletion)

另外一个可行的思路，与target距离为K的点的集合分为两部分【target的子节点】和【非target的子节点】

打个比方，【target的子节点】就是从target往下的第K层的节点。【非target的子节点】的则是【target的父节点下面，非target这侧往下第K-1层的节点】+【target的父节的父节点下面，非target父节点这侧往下第K-2层的节点】+……

依次类推直到到达根节点

import java.util.*;

/**
 * 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) {
        parentMap = new HashMap<>();
        dfs(root, null);
        goToK(target,null,k,0);
        TreeNode parent = parentMap.get(target);
        TreeNode excludeTarget = target;
        int distance = 0;
        while (null!= parent){
            distance++;
            goToK(parent,excludeTarget,k,distance);
            excludeTarget = parent;
            parent = parentMap.get(parent);
        }
        return res;
    }

    private void goToK(TreeNode node, TreeNode excludeTarget, int k, int distance){
        if (node==null){
            return;
        }
        if (null!= excludeTarget && node.val==excludeTarget.val){
            return;
        }
        if (k==distance){
            res.add(node.val);
            return;
        }
        distance = distance+1;
        goToK(node.left,excludeTarget,k,distance);
        goToK(node.right,excludeTarget,k,distance);
    }
    
    
    public void dfs(TreeNode node, TreeNode parent) {
            parentMap.put(node, parent);
            if (node.right!=null){
                dfs(node.right, node);
            }
            if (node.left!=null){
                dfs(node.left, node);
            }
    }


    Map<TreeNode, TreeNode> parentMap;

    private List<Integer> res = new ArrayList<>();

}
//leetcode submit region end(Prohibit modification and deletion)