308. All Nodes Distance K in Binary Tree

Build a parent map so we can traverse up. Then BFS from target for k levels.

Approach

1. DFS to build a parent pointer map.
2. BFS from target node, expanding to left, right, and parent.
3. After k levels, all nodes in the queue are the answer.

Complexity

• Time: O(n)
• Space: O(n)

import java.util.*;

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        buildGraph(root, null, graph);

        Set<Integer> visited = new HashSet<>();
        visited.add(target.val);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target.val);

        for (int i = 0; i < k; i++) {
            int size = queue.size();
            Queue<Integer> nextQueue = new LinkedList<>();
            for (int j = 0; j < size; j++) {
                int node = queue.poll();
                for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        nextQueue.add(neighbor);
                    }
                }
            }
            queue = nextQueue;
        }

        return new ArrayList<>(queue);
    }

    private void buildGraph(TreeNode node, TreeNode parent, Map<Integer, List<Integer>> graph) {
        if (node == null) return;
        if (parent != null) {
            graph.computeIfAbsent(node.val, k -> new ArrayList<>()).add(parent.val);
            graph.computeIfAbsent(parent.val, k -> new ArrayList<>()).add(node.val);
        }
        buildGraph(node.left, node, graph);
        buildGraph(node.right, node, graph);
    }
}