定一個(gè)二叉樹（具有根結(jié)點(diǎn)?root），?一個(gè)目標(biāo)結(jié)點(diǎn)?target?，和一個(gè)整數(shù)值 K 。

返回到目標(biāo)結(jié)點(diǎn) target 距離為 K 的所有結(jié)點(diǎn)的值的列表。 答案可以以任何順序返回。

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

? ? ? ? ? ? ? 輸出：[7,4,1]

解釋：? 所求結(jié)點(diǎn)為與目標(biāo)結(jié)點(diǎn)（值為 5）距離為 2 的結(jié)點(diǎn)，

? ? ? ? ? ? ?值分別為 7，4，以及 1

解題思路：?target 已知，從target 出發(fā)，使用深度優(yōu)先搜索去尋找與target 距離為 k 的所有結(jié)點(diǎn)，即深度為 k 的所有結(jié)點(diǎn)。

? ? ? ? ? ? ? ? ? ?可知要尋找與target距離為k的結(jié)點(diǎn)，不應(yīng)該只往子節(jié)點(diǎn)深度遍歷，也要去深度遍歷父節(jié)點(diǎn)。

? ? ? ? ? ? ? ? ? ?用一個(gè)哈希表記錄每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)， 即創(chuàng)建hashMap，key表示子節(jié)點(diǎn)的值，value表示該子節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)。

? ? ? ? ? ? ? ? ? ?因?yàn)榧幢闅v子節(jié)點(diǎn)也遍歷父節(jié)點(diǎn)，可能會(huì)重復(fù)訪問(wèn)結(jié)點(diǎn)，為避免在深度優(yōu)先搜索時(shí)重復(fù)訪問(wèn)結(jié)點(diǎn)，遞歸時(shí)額外傳入來(lái)源結(jié)點(diǎn)from，在遞歸前比較目標(biāo)結(jié)點(diǎn)是否與來(lái)源結(jié)點(diǎn)相同，不同的情況下才進(jìn)行遞歸。

class?Solution?{

????Map<Integer,?TreeNode>?hashParent?=?new?HashMap<Integer,?TreeNode>(); // 哈希表記錄每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)

????List<Integer>?returnList?=?new?ArrayList<Integer>(); //要返回的所有的節(jié)點(diǎn)的值，即到target距離為K的所有結(jié)點(diǎn)

????public?List<Integer>?distanceK(TreeNode?root,?TreeNode?target,?int?k)?{

????????findParent(root);

????????findReturnList(target,?null,?0,?k);

????????return?returnList;

????}

????public?void?findParent(TreeNode?node)?{ // 創(chuàng)建子節(jié)點(diǎn)-父節(jié)點(diǎn)hash表

????????if?(node.left?!=?null)?{

????????????hashParent.put(node.left.val,?node);

????????????findParent(node.left);

????????}

????????if?(node.right?!=?null)?{

????????????hashParent.put(node.right.val,?node);

????????????findParent(node.right);

????????}

????}

????public?void?findReturnList(TreeNode?root,?TreeNode?from,?int?depth,?int?k)?{ // 深度優(yōu)先遍歷

????????if(root?==?null)?{? //遍歷到空結(jié)點(diǎn)，停止遍歷；

????????????return;

????????}

????????if(depth?==?k)?{ //遍歷到深度為k，停止遍歷；

????????????returnList.add(root.val);

????????????return;

????????}

????????if(root.left?!=?from)?{ //即將要訪問(wèn)的左節(jié)點(diǎn)不是來(lái)源結(jié)點(diǎn)from

????????????findReturnList(root.left,?root,?depth+1,?k); //深度遍歷左節(jié)點(diǎn)

????????}

????????if(root.right?!=?from)?{? //即將要訪問(wèn)的右節(jié)點(diǎn)不是來(lái)源結(jié)點(diǎn)from

????????????findReturnList(root.right,?root,?depth+1,?k);? //深度遍歷右節(jié)點(diǎn)

????????}

????????if(hashParent.get(root.val)?!=?from)?{? ?//即將要訪問(wèn)的父節(jié)點(diǎn)節(jié)點(diǎn)不是來(lái)源結(jié)點(diǎn)from

????????????findReturnList(hashParent.get(root.val),?root,?depth+1,?k); // //深度遍歷父節(jié)點(diǎn)

????????}

????}

}