题解 | #距离是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 {
    
    public ArrayList<Integer> res = new ArrayList<>();
    public int target = 0;
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @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
        this.target = target;
        TreeNode targetNode = findTarget(root);
        HashMap<TreeNode, TreeNode> fatherNodes = getFatherNodes(root);
        TreeNode startNode = targetNode;
        process(startNode, k);
        k--;
        while (k >= 0) {
            
            if (startNode == root) {
                break;
            }
            
            if (k == 0) {
                res.add(fatherNodes.get(startNode).val);
                break;
            }
            
            TreeNode fatherNode = fatherNodes.get(startNode);
            if (startNode == fatherNode.left && k - 1 >= 0) {
                process(fatherNode.right, k - 1);
            }
            if (startNode == fatherNode.right && k - 1 >= 0) {
                process(fatherNode.left, k - 1);
            }
            startNode = fatherNode;
            k--;
            

        }
        return res;
    }
    
    public TreeNode findTarget(TreeNode node) {
        if (null == node) {
            return null;
        }
        if (node.val == target) {
            return node;
        }
        TreeNode leftNode = findTarget(node.left);
        TreeNode rightNode = findTarget(node.right);
        return leftNode == null ? rightNode : leftNode;
    }
    
    public HashMap<TreeNode, TreeNode> getFatherNodes(TreeNode root) {
        HashMap<TreeNode, TreeNode> fatherNodes = new HashMap<>();
        fatherNodes.put(root, root);
        TreeNode node = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (null != node.left) {
                queue.add(node.left);
                fatherNodes.put(node.left, node);
            }
            if (null != node.right) {
                queue.add(node.right);
                fatherNodes.put(node.right, node);
            }
        }
        return fatherNodes;
    }
    
    public void process(TreeNode node, int k) {
        if (null == node) {
            return;
        }
        if (k == 0) {
            if (node.val != target) {
                res.add(node.val);
            }
            return;
        }
        process(node.left, k - 1);
        process(node.right, k - 1);
    }
}