The key to solve this problem is to find the path from root to target, and put the length to target of every node from root to target to a map.
Then either using BFS or using DFS depends on you.
BFS:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> distanceK(TreeNode root, TreeNode target, int k) { Map<Integer, Integer> map = new HashMap<>(); preOrder(root, target.val, map); bfs(root, k, map); return res; } private void bfs(TreeNode root, int k, Map<Integer, Integer> map){ Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i=0;i<size;i++){ TreeNode node = queue.poll(); int len=0; if(map.containsKey(node.val)){ len = map.get(node.val); if(len==k){ res.add(node.val); } } if(node.left!=null){ if(!map.containsKey(node.left.val)) map.put(node.left.val, len+1); queue.offer(node.left); } if(node.right!=null){ if(!map.containsKey(node.right.val)) map.put(node.right.val, len+1); queue.offer(node.right); } } } } private int preOrder(TreeNode root, int target, Map<Integer, Integer> map){ if(root==null) return -1; if(root.val==target){ map.put(root.val, 0); return 0; } int left = preOrder(root.left, target, map); int right = preOrder(root.right, target, map); if(left>=0){ map.put(root.val, left+1); return left+1; } if(right>=0){ map.put(root.val, right+1); return right+1; } return -1; } }
DFS:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> distanceK(TreeNode root, TreeNode target, int k) { Map<Integer, Integer> map = new HashMap<>(); preOrder(root, target.val, map); dfs(root, k, map); return res; } private void dfs(TreeNode root, int k, Map<Integer, Integer> map){ if(map.get(root.val)==k){ res.add(root.val); } if(root.left!=null){ if(!map.containsKey(root.left.val)){ map.put(root.left.val, map.get(root.val)+1); } dfs(root.left, k, map); } if(root.right!=null){ if(!map.containsKey(root.right.val)){ map.put(root.right.val, map.get(root.val)+1); } dfs(root.right, k, map); } } private int preOrder(TreeNode root, int target, Map<Integer, Integer> map){ if(root==null) return -1; if(root.val==target){ map.put(root.val, 0); return 0; } int left = preOrder(root.left, target, map); int right = preOrder(root.right, target, map); if(left>=0){ map.put(root.val, left+1); return left+1; } if(right>=0){ map.put(root.val, right+1); return right+1; } return -1; } }