863. 二叉树中所有距离为 K 的结点
思路：DFS+哈希
第一次DFS来用哈希表存储节点和其父节点这样就可以在之后回溯得到距离为k的点
第二次DFS从target开始，以target为root，这样就可以用递归来找当前depth和k相同的节点了，需要注意的是，在回溯过程中会出现遍历过已经出现的数字的情况，因此我们需要记录下之前的节点是哪个。
ps:由于节点的值都不相同因此hashmap的key选择了值
代码：
<![CDATA[
// /**
// * Definition for a binary tree node.
// * public class TreeNode {
// * int val;
// * TreeNode left;
// * TreeNode right;
// * TreeNode(int x) { val = x; }
// * }
// */
class Solution {
Map<Integer, TreeNode> hm = new HashMap<Integer, TreeNode>();
List<Integer> ret = new ArrayList<Integer>();
public void DFS_Hash(TreeNode root){
if(root==null) return;
if(root.left!=null){
hm.put(root.left.val, root);
DFS_Hash(root.left);
}
if(root.right!=null){
hm.put(root.right.val, root);
DFS_Hash(root.right);
}
}
public void DFS_Depth( TreeNode target, int cur_k, int k, int t){
if(target==null) return;
// int temp = k;
// TreeNode temp_target = target;
// if(root.val==target.val){
// while(k>0){
// // 通过哈希表得到target的父节点:
// TreeNode res = hm.get(temp_target.val);
// temp_target = res;
// k--;
// }
// ret.add(res.val);
// k = temp;
// }
// System.out.println(target.val+" "+t);
if(cur_k==k){
// System.out.println(target.val);
ret.add(target.val);
return;
}
if(target.left!=null && target.left.val!=t){
DFS_Depth(target.left, cur_k+1, k, target.val);
}
// System.out.println(target.right);
if(target.right!=null && target.right.val!=t){
DFS_Depth(target.right, cur_k+1, k, target.val);
}
if(hm.get(target.val)!=null && hm.get(target.val).val !=t ){
// System.out.println(hm.get(target.val).val+" "+t);
DFS_Depth(hm.get(target.val), cur_k+1, k, target.val);
}
}
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
DFS_Hash(root);
// System.out.println(hm.toString());
DFS_Depth(target, 0, k, target.val);
return ret;
}
}
]]>
官方答案：
<![CDATA[
class Solution {
Map<Integer, TreeNode> parents = new HashMap<Integer, TreeNode>();
List<Integer> ans = new ArrayList<Integer>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
// 从 root 出发 DFS，记录每个结点的父结点
findParents(root);
// 从 target 出发 DFS，寻找所有深度为 k 的结点
findAns(target, null, 0, k);
return ans;
}
public void findParents(TreeNode node) {
if (node.left != null) {
parents.put(node.left.val, node);
findParents(node.left);
}
if (node.right != null) {
parents.put(node.right.val, node);
findParents(node.right);
}
}
public void findAns(TreeNode node, TreeNode from, int depth, int k) {
if (node == null) {
return;
}
if (depth == k) {
ans.add(node.val);
return;
}
if (node.left != from) {
findAns(node.left, node, depth + 1, k);
}
if (node.right != from) {
findAns(node.right, node, depth + 1, k);
}
if (parents.get(node.val) != from) {
findAns(parents.get(node.val), node, depth + 1, k);
}
}
}
]]>
