Solved! Leetcode 863. All Nodes Distance K in Binary Tree

source: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/

All Nodes Distance K in Binary Tree

Description

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

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, TreeNode> parentMap = new HashMap<>();  
    public List<Integer> distanceK(TreeNode  root, TreeNode  target, int k) {
        dfs(root, null);
        List<Integer> list = bfs(target, k);
        return list;
    }

    //perform bfs starting from target node and add all the nodes that are k distance from the target 
    //into a list
    private List<Integer> bfs(TreeNode target, int k){
        Set<TreeNode> seen = new HashSet<>();

        Queue<TreeNode> next = new LinkedList<>();
        Queue<TreeNode> curr = null;

        next.offer(target);
        seen.add(target);
        int distance = 0;
        List<Integer> res = new ArrayList<>();
        while(!next.isEmpty()){
            curr = next;
            next = new LinkedList<>();
            while(!curr.isEmpty()){
                TreeNode node = curr.poll();
                if(node!=null){
                    if(distance==k){
                        res.add(node.val);
                    } else {
                        if(!seen.contains(node.left)){
                            seen.add(node.left);
                            next.offer(node.left);
                        }
                        if(!seen.contains(node.right)){
                            seen.add(node.right);
                            next.offer(node.right);
                        }
                        TreeNode parent = parentMap.get(node.val);
                        if(!seen.contains(parent)){
                            seen.add(parent);
                            next.offer(parent);
                        }
                    }
                }
            }
            if(distance==k)
            {
                return res;
            }
            distance++;
        }

        return res;
    }

    //populate parent map
    private void dfs(TreeNode node, TreeNode parent){
        if(node==null)
            return;
        parentMap.put(node.val, parent);
        dfs(node.left, node);
        dfs(node.right, node);
    }
}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

class Solution {

Map<Integer, TreeNode> parentMap = new HashMap<>();

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {

dfs(root, null);

List<Integer> list = bfs(target, k);

return list;

}

//perform bfs starting from target node and add all the nodes that are k distance from the target

//into a list

private List<Integer> bfs(TreeNode target, int k){

Set<TreeNode> seen = new HashSet<>();

Queue<TreeNode> next = new LinkedList<>();

Queue<TreeNode> curr = null;

next.offer(target);

seen.add(target);

int distance = 0;

List<Integer> res = new ArrayList<>();

while(!next.isEmpty()){

curr = next;

next = new LinkedList<>();

while(!curr.isEmpty()){

TreeNode node = curr.poll();

if(node!=null){

if(distance==k){

res.add(node.val);

} else {

if(!seen.contains(node.left)){

seen.add(node.left);

next.offer(node.left);

}

if(!seen.contains(node.right)){

seen.add(node.right);

next.offer(node.right);

}

TreeNode parent = parentMap.get(node.val);

if(!seen.contains(parent)){

seen.add(parent);

next.offer(parent);

}

if(distance==k)

{

return res;

}

distance++;

}

return res;

}

//populate parent map

private void dfs(TreeNode node, TreeNode parent){

if(node==null)

return;

parentMap.put(node.val, parent);

dfs(node.left, node);

dfs(node.right, node);

}

Rate this post

Coddicted