All Nodes Distance K in Binary Tree

Medium

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node.  The answer can be returned in any order.

[1,7 and 4] are in k = 2 distance from the node 5

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.

Note:

  1. The given tree is non-empty.
  2. Each node in the tree has unique values 0 <= node.val <= 500.
  3. The target node is a node in the tree.
  4. 0 <= K <= 1000.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        if(K == 0){
            result.add(target.val);
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(target);
        queue.offer(null);
        Set<TreeNode> seen = new HashSet<>();
        seen.add(target);
        seen.add(null);
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        DFS(root, parentMap);
        while(!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            if(curNode == null){// branch
                K--;
                if(K == 0){
                    while(!queue.isEmpty()){
                        result.add(queue.poll().val);
                    }
                    return result;
                }
                queue.offer(null);
                
            }else{
                if(!seen.contains(curNode.left)){
                    queue.offer(curNode.left);
                    seen.add(curNode.left);
                }
                if(!seen.contains(curNode.right)){
                    queue.offer(curNode.right);
                    seen.add(curNode.right);
                }
                TreeNode parent = parentMap.get(curNode);
                if(!seen.contains(parent)){
                    queue.offer(parent);
                    seen.add(parent);
                }
            }
        }
        return null;
    }
    
    private void DFS(TreeNode node, Map<TreeNode, TreeNode> parentMap){
        if(node == null){
            return;
        }
        if(node.left != null) parentMap.put(node.left, node);
        if(node.right != null) parentMap.put(node.right, node);
        DFS(node.left, parentMap);
        DFS(node.right, parentMap);
    }
}

Categories: Binary Tree

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s