一、题目

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

点击查看原题
难度级别： 中等

二、思路

1）哈希表+深度搜索

如果使用递归的方式查找到target节点上方或旁边距离为k的节点，逻辑比较复杂
于是使用哈希表建立起来子节点与父节点的映射关系，二叉树就变成了三叉树，只需要以target节点为root，进行深度搜索，就可以找到距离k的所有节点（tips：记录一下遍历过来的上一个节点，防止重复遍历）

三、代码

1）哈希表+深度搜索

  1. class Solution {
  2.     Map<TreeNode, TreeNode> map;
  3.     List<Integer> ans;
  4.     public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
  5.         ans = new ArrayList();
  6.         map = new HashMap();
  7.         findParents(root);
  8.         findChildren(target, null, k);
  9.         return ans;
  10.     }
  11.     private void findParents(TreeNode root) {
  12.         if (root.left != null) {
  13.             map.put(root.left, root);
  14.             findParents(root.left);
  15.         }
  16.         if (root.right != null) {
  17.             map.put(root.right, root);
  18.             findParents(root.right);
  19.         }
  20.     }
  21.     private void findChildren(TreeNode root, TreeNode from, int k) {
  22.         if (root == null) {
  23.             return ;
  24.         }
  25.         if (k == 0) {
  26.             ans.add(root.val);
  27.             return ;
  28.         }
  29.         if (root.left != from) {
  30.             findChildren(root.left, root, k - 1);
  31.         }
  32.         if (root.right != from) {
  33.             findChildren(root.right, root, k - 1);
  34.         }
  35.         if (map.get(root) != from) {
  36.             findChildren(map.get(root), root, k - 1);
  37.         }
  38.     }
  39. }

时间复杂度为O(n)，空间复杂度为O(n)