Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
You can return the answer in any order.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Example 2:
Input: root = [1], target = 1, k = 3
Output: []
Constraints:
The number of nodes in the tree is in the range [1, 500].
0 <= Node.val <= 500
All the values Node.val are unique.
target is the value of one of the nodes in the tree.
0 <= k <= 1000
Solutions
Solution 1: DFS + Hash Table
We first use DFS to traverse the entire tree and save each node's parent node in the hash table \(\textit{g}\).
Next, we use DFS again, starting from \(\textit{target}\), to search for nodes at a distance of \(k\) both upwards and downwards, and add them to the result array.
The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of nodes in the binary tree.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution{privateMap<TreeNode,TreeNode>g=newHashMap<>();privateList<Integer>ans=newArrayList<>();publicList<Integer>distanceK(TreeNoderoot,TreeNodetarget,intk){dfs(root,null);dfs2(target,null,k);returnans;}privatevoiddfs(TreeNoderoot,TreeNodefa){if(root==null){return;}g.put(root,fa);dfs(root.left,root);dfs(root.right,root);}privatevoiddfs2(TreeNoderoot,TreeNodefa,intk){if(root==null){return;}if(k==0){ans.add(root.val);return;}for(TreeNodenxt:newTreeNode[]{root.left,root.right,g.get(root)}){if(nxt!=fa){dfs2(nxt,root,k-1);}}}}