All nodes with distance K in a binary tree

Topic describes

Answer key

Use a map to record the parent of each node, and then have DFS start at target (assuming target is the root), and recursively record the depth, as long as the depth is equal to k, that is, the distance from target is equal to k, which can be stored in list.

Execution time: 14 ms, beating 74.54% of all Java commits

Memory consumption: 38.1 MB, beating 98.78% of all Java commits

class Solution{ List<Integer> res = new ArrayList<>(); Map<TreeNode, TreeNode> map = new HashMap<>(); // <root, parent> Set<TreeNode> set = new HashSet<>(); int k; public List<Integer> distanceK (TreeNode root, TreeNode target, int k){ this.k = k; findParent(root, null); dfs(target, target, 0); return res; } public void findParent(TreeNode root, TreeNode parent) { if (root == null) return; map.put(root, parent); findParent(root.left, root); findParent(root.right, root); } public void dfs(TreeNode root, TreeNode target, int depth) { if (root == null || set.contains(root)) { return; } set.add(root); if (depth == k) { res.add(root.val); return; } // System.out.println(root.val + " " + depth); dfs(root.left, target, depth + 1); dfs(root.right, target, depth + 1); dfs(map.get(root), target, depth + 1); }}Copy the code