二叉树中所有距离为 K 的结点

/*
 * 思路：
 * 1. 将二叉树转化为图结构，使用Map存储每个结点和其相邻的结点。
 * 2. 使用BFS遍历图找到距离为k的所有结点。
 */

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

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

public class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
        buildGraph(root, null, graph);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(target);
        Set<TreeNode> visited = new HashSet<>();
        visited.add(target);
        int distance = 0;
        while (!queue.isEmpty()) {
            if (distance == k) break;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                for (TreeNode neighbor : graph.get(node)) {
                    if (visited.add(neighbor)) {
                        queue.add(neighbor);
                    }
                }
            }
            distance++;
        }
        return queue.stream().map(node -> node.val).collect(Collectors.toList());
    }

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