1ms beat 100% simple Java dfs with(without) hashmap, including explanation
As we know, if the distance from a node to target node is k, the distance from its child to the target node is k + 1 unless the child node is closer to the targ
As we know, if the distance from a node to target node is `k`, the distance from its child to the target node is `k + 1` **unless** the child node is closer to the target node which means the target node is in it\'s subtree.\n\nTo avoid this situation, we need to travel the tree first to find the path from `root` to `target`, to:\n* store the value of distance in hashamp from the `all nodes in that path` to `target`\n\nThen we can easily use dfs to travel the whole tree. Every time when we meet a treenode which has already been stored in map, use the stored value in hashmap **instead of** plus 1.\n\nTime Complexity: O(n)\n\n\n```Java\nclass Solution {\n    \n    Map<TreeNode, Integer> map = new HashMap<>();\n        \n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> res = new LinkedList<>();\n        find(root, target);\n        dfs(root, target, K, map.get(root), res);\n        return res;\n    }\n    \n    // find target node first and store the distance in that path that we could use it later directly\n    private int find(TreeNode root, TreeNode target) {\n        if (root == null) return -1;\n        if (root == target) {\n            map.put(root, 0);\n            return 0;\n        }\n        int left = find(root.left, target);\n        if (left >= 0) {\n            map.put(root, left + 1);\n            return left + 1;\n        }\n\t\tint right = find(root.right, target);\n\t\tif (right >= 0) {\n            map.put(root, right + 1);\n            return right + 1;\n        }\n        return -1;\n    }\n    \n    private void dfs(TreeNode root, TreeNode target, int K, int length, List<Integer> res) {\n        if (root == null) return;\n        if (map.containsKey(root)) length = map.get(root);\n        if (length == K) res.add(root.val);\n        dfs(root.left, target, K, length + 1, res);\n        dfs(root.right, target, K, length + 1, res);\n    }\n}\n```\n\n--------------------------------------------------------------------------\n**version** without using hashmap: same idea, combine two recursive function\n\n```Java\nclass Solution {\n            \n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> res = new LinkedList<>();\n        if (K == 0) {\n            res.add(target.val);\n        } else {\n            dfs(res, root, target.val, K ,0);\n        }\n        return res;\n    }\n    \n    private int dfs(List<Integer> res, TreeNode node, int target, int K, int depth) {\n        if (node == null) return 0;\n        \n        if (depth == K) {\n            res.add(node.val);\n            return 0;\n        }\n        \n        int left, right;\n        if (node.val == target || depth > 0) {\n            left = dfs(res, node.left, target, K, depth + 1);\n            right = dfs(res, node.right, target, K, depth + 1);\n        } else {\n            left = dfs(res, node.left, target, K, depth);\n            right = dfs(res, node.right, target, K, depth);\n        }\n        \n        if (node.val == target) return 1;\n        \n        if (left == K || right == K) {\n            res.add(node.val);\n            return 0;\n        }\n        \n        if (left > 0) {\n            dfs(res, node.right, target, K, left + 1);\n            return left + 1;\n        }\n        \n        if (right > 0) {\n            dfs(res, node.left, target, K, right + 1);\n            return right + 1;\n        }\n        \n        return 0;\n    }\n}\n```
[]