Java Intuitive Solutions
Idea\n Note the distances from target node to all the nodes up the path to root from target in a map.\n Apply pre-order traversal using the map above.\n\t If th
**Idea**\n* Note the distances from target node to all the nodes up the path to root from target in a map.\n* Apply pre-order traversal using the map above.\n\t* If the node is present in the map, use that distance\n\t* else assume `d+1` where d = distance for the parent.\n\n```\npublic List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> list = new LinkedList<>();\n        Map<TreeNode, Integer> dist = new HashMap<>();\n        findTargetPath(root, target, dist);\n        preorder(root, 0, K, list, dist);\n        return list;\n    }\n    private int findTargetPath(TreeNode curr, TreeNode target, Map<TreeNode, Integer> dist){\n        if(curr == null) return -1;\n        if(curr == target){\n            dist.put(curr, 0);\n            return 0;\n        }\n        int val = findTargetPath(curr.left, target, dist);\n        if(val == -1)\n            val = findTargetPath(curr.right, target, dist);\n        if(val == -1)\n            return -1;\n        //for parent\n        val += 1;\n        dist.put(curr, val);\n        return val;\n    }\n    private void preorder(TreeNode curr, int d, int k, List<Integer> list, Map<TreeNode, Integer> dist){\n        if(curr == null) return;\n        d = dist.getOrDefault(curr, d+1);\n        if(d == k)\n            list.add(curr.val);\n        preorder(curr.left, d, k, list, dist);\n        preorder(curr.right, d, k, list, dist);\n    }\n```\n----\n\n**Solution2**\nThe key problem is to solve how to deal with nodes which are not descendents of `target` node. For descendents, it is trivial `dfs`.\nMy idea is to treat the tree more like a graph meaning if there is a way to go up the path from the `target` then we can know the distances of those nodes that are not descendents of target, correct?\nSo why not build a parent-child map only for that path (path from root to target)? Once we have it, the problem just needs a dfs on "graph" and collect nodes at distance `k`.\n\n```\nclass Solution {\n    Map<TreeNode, TreeNode> p = null;\n    List<Integer> list = new ArrayList<>();\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        buildParents(root, target, new HashMap<>());\n        dfs(target, null, 0, k);\n        return list;\n    }\n    private void dfs(TreeNode curr, TreeNode parent, int d, int k){\n        if(curr == null) return;\n        if(d == k){\n            list.add(curr.val);\n            return;\n        }\n        if(curr.left != parent)\n            dfs(curr.left, curr, d+1, k);\n        if(curr.right != parent)\n            dfs(curr.right, curr, d+1, k);\n        dfs(p.getOrDefault(curr, null), curr, d+1, k);\n    }\n    private boolean buildParents(TreeNode curr, TreeNode t, Map<TreeNode, TreeNode> tmp){\n        if(curr == null) return false;\n        if(curr == t){\n            p = new HashMap<>(tmp);\n            return true;\n        }\n        boolean ret = false;\n        if(curr.left != null){\n            tmp.put(curr.left, curr);\n            ret = buildParents(curr.left, t, tmp);\n            tmp.remove(curr.left);\n        }\n        if(!ret && curr.right != null){\n            tmp.put(curr.right, curr);\n            ret = buildParents(curr.right, t, tmp);\n            tmp.remove(curr.right);\n        }\n        return ret;\n    }\n}\n```
[]