距离是K的二叉树节点

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