距离是K的二叉树节点

import java.util.*;

// 以节点target 为根,       下面第k层节点
// 以节点target 父节点 为根, 下面第k-1层节点
// 父父节点, k-2层 ...  循环
//
// Map存父节点
public class Solution {
    ArrayList<Integer> res = new ArrayList<>();  // 结果
    Set<TreeNode> parent = new HashSet<>(); // target及父节点

    public ArrayList<Integer> distanceKnodes (TreeNode root, int target, int k) {
        // BFS: 找到target节点及其父节点
        Map<TreeNode, TreeNode> map = new HashMap<>(); // 存父节点
        map.put(root, null);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode targetNode = null; // target节点
        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            if (t.val == target) {
                targetNode = t;
                break;
            }
            if (t.left  != null) {
                map.put(t.left, t);
                queue.offer(t.left);
            }
            if (t.right != null) {
                map.put(t.right, t);
                queue.offer(t.right);
            }
        }
        // target及父节点
        TreeNode p = targetNode;
        while (p != null) {
            parent.add(p);
            p = map.get(p);
        }
        // 循环：target节点为根 下面k层节点, 父 k-1, 父父 k-2...
        if (k == 0) res.add(target); // k==0 特判target
        p = targetNode;
        while (p != null) {
            bfs(p, k, target); // 调用
            p = map.get(p);
            k--;
        }
        
        return res;
    }

    // BFS: 以root为根, 下面第k层节点 (排除target及其父节点那侧子树🍓)
    void bfs(TreeNode root, int k, int target) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty() && level <= k + 1) {
            level++;
            int size = queue.size();
            while (size-- > 0) {
                TreeNode t = queue.poll();
                if (level == k + 1) { // 下面第k层节点
                    res.add(t.val);
                }
                // 排除target及其父节点 那个子树分支（因为会重复计算,上去时已算过一部分路径了）
                if (t.left  != null && !parent.contains(t.left))  queue.offer(t.left);
                if (t.right != null && !parent.contains(t.right)) queue.offer(t.right);
            }
        }
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC370 距离是K的二叉树节点
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param target int整型
     * @param k int整型
     * @return int整型一维数组
     */
    public ArrayList<Integer> distanceKnodes (TreeNode root, int target, int k) {
        // return solution1(root, target, k);
        return solution2(root, target, k);
    }

    private HashSet<Integer>[] adj;
    private boolean[] isVisited;
    private ArrayList<Integer> result = new ArrayList<>();
    private final int N = 1000;

    /**
     * 后序遍历 + 层序遍历
     * 
     * 图模型
     * 
     * @param root
     * @param target
     * @param k
     * @return
     */
    private ArrayList<Integer> solution1(TreeNode root, int target, int k){
        isVisited = new boolean[N];
        adj = new HashSet[N];
        for(int i = 0; i < N; i++){
            adj[i] = new HashSet<>();
        }

        postOrder(root);
        levelOrder(target, k);

        return result;
    }

    /**
     * 递归: 后序遍历
     * @param root
     */
    private void postOrder(TreeNode root){
        if(root == null){
            return;
        }

        postOrder(root.left);
        postOrder(root.right);

        if(root.left != null){
            adj[root.val].add(root.left.val);
            adj[root.left.val].add(root.val);
        }
        if(root.right != null){
            adj[root.val].add(root.right.val);
            adj[root.right.val].add(root.val);
        }
    }

    /**
     * 队列: 层序遍历
     * @param target
     * @param k
     */
    private void levelOrder(int target, int k){
        Queue<Integer> queue = new LinkedList<>();
        isVisited[target] = true;
        queue.offer(target);

        int curr;
        int size;
        int level = 0;
        boolean isFound = false;
        while(!queue.isEmpty()){
            level++;
            size = queue.size();
            while(size-- > 0){
                curr = queue.poll();
                for(int next: adj[curr]){
                    if(!isVisited[next]){
                        isVisited[next] = true;
                        if(level == k){
                            isFound = true;
                            result.add(next);
                        }else{
                            queue.offer(next);
                        }
                    }
                }
            }
            if(isFound){
                break;
            }
        }
    }

    //////////////////////////////////////////////////////////////////////////////////////////

    private ArrayList<Integer> list = new ArrayList<>();
    private HashMap<Integer,TreeNode> parentMap = new HashMap<>();

    /**
     * 层序遍历 + 前序遍历
     * @param root
     * @param target
     * @param k
     * @return
     */
    private ArrayList<Integer> solution2(TreeNode root, int target, int k){
        if(root == null){
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        parentMap.put(root.val, null);


        TreeNode node,cNode,pNode;
        while(!queue.isEmpty()){
            node = queue.poll();
            if(node.val == target){
                if(k == 0){
                    list.add(node.val);
                    return list;
                }
                downKnodes(node, k);
                cNode = node;
                pNode = parentMap.get(cNode.val);
                while(pNode!=null && k>0){
                    upKnodes(cNode, pNode, --k);
                    cNode = pNode;
                    pNode = parentMap.get(cNode.val);
                }

                return list;
            }
            if(node.left != null){
                parentMap.put(node.left.val, node);
                queue.offer(node.left);
            }
            if(node.right != null){
                parentMap.put(node.right.val, node);
                queue.offer(node.right);
            }
        }

        return list;
    }

    /**
     * 向上遍历
     * @param cNode
     * @param pNode
     * @param k
     */
    private void upKnodes(TreeNode cNode, TreeNode pNode, int k){
        if(k == 0){
            list.add(pNode.val);
            return;
        }

        if(pNode.left!=null && pNode.left.val!=cNode.val){
            downKnodes(pNode.left, k-1);
        }

        if(pNode.right!=null && pNode.right.val!=cNode.val){
            downKnodes(pNode.right, k-1);
        }
    }

    /**
     * 向下遍历
     * @param root
     * @param k
     */
    private void downKnodes(TreeNode root, int k){
        preOrder(root, k);
    }

    /**
     * 前序遍历
     * @param root
     * @param k
     */
    private void preOrder(TreeNode root, int k){
        if(root == null){
            return;
        }

        if(k == 0){
            list.add(root.val);
            return;
        }

        preOrder(root.left, k-1);
        preOrder(root.right, k-1);
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param target int整型 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> distanceKnodes(TreeNode root, int target, int k) {
        // write code here
        if (root == null) {
            return new ArrayList<>();
        }
        // 最终返回的结果
        Set<Integer> finalRes = new HashSet<>();
        // 记录dfs遍历的所有路径
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // dfs遍历路径
        dfs(root, new ArrayList<>(), result);

        // 记录已经处理过的节点，理论上后续处理过的节点所在的路径无需再次处理
        ArrayList<Integer> processNode = new ArrayList<>();
        int father = target;
        while (k > 0) {
            judgeNode(finalRes, k--, result, processNode, father);
            // 加入到已处理集合
            processNode.add(father);
            // 找到新的父节点
            father = getFather(result, father);
        }
        return new ArrayList<>(finalRes);
    }

    private boolean alreadyChoose(ArrayList<Integer> processNodes, ArrayList<Integer> integers) {
        for (Integer processNode : processNodes) {
            if (integers.contains(processNode)) {
                return true;
            }
        }
        return false;
    }

    private void judgeNode(Set<Integer> finalRes, int k, ArrayList<ArrayList<Integer>> result,
                           ArrayList<Integer> processFather, int father) {
        for (ArrayList<Integer> integers : result) {
            if (alreadyChoose(processFather, integers)) {
                continue;
            }
            // 根节点，仅需处理未处理过的孩子
            if (father == -1) {
                if (k < integers.size()) {
                    finalRes.add(integers.get(k));
                }
            } else {
                // 非根节点，需处理包含father节点的路径
                if (integers.contains(father)) {
                    int index = integers.indexOf(father);
                    if (index + k < integers.size()) {
                        finalRes.add(integers.get(index + k));
                    }
                    if (index - k >= 0) {
                        finalRes.add(integers.get(index - k));
                    }
                }
            }

        }
    }

    /**
     * 获取当前处理节点的父节点
     * @param result
     * @param target
     * @return
     */
    private int getFather(ArrayList<ArrayList<Integer>> result, int target) {
        for (ArrayList<Integer> res : result) {
            if (res.contains(target)) {
                int index = res.indexOf(target);
                if (index - 1 >= 0) {
                    return res.get(index - 1);
                }
            }
        }
        // 已经是树根了，无父节点
        return -1;
    }

    private void dfs(TreeNode root, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result) {
        list.add(root.val);

        if (root.left == null && root.right == null) {
            result.add(new ArrayList<>(list));
            return;
        }

        if (root.left != null) {
            dfs(root.left, list, result);
            list.remove(list.size() - 1);
        }
        if (root.right != null) {
            dfs(root.right, list, result);
            list.remove(list.size() - 1);
        }
    }
}