0863. 二叉树中所有距离为 K 的结点【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS 建图 + BFS

1. 📝 题目描述

• leetcode

给定一个二叉树（具有根结点 root）， 一个目标结点 target，和一个整数值 k，返回到目标结点 target 距离为 k 的所有结点的值的数组。

答案可以以 任何顺序 返回。

---

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

示例 2：

输入: root = [1], target = 1, k = 3
输出: []

---

提示：

• 节点数在 [1, 500] 范围内
• 0 <= Node.val <= 500
• Node.val 中所有值 不同
• 目标结点 target 是树上的结点。
• 0 <= k <= 1000

2. 🎯 s.1 - DFS 建图 + BFS

c

void buildGraph(struct TreeNode* node, struct TreeNode* parent, int graph[][3], int* graphSize) {
    if (!node) return;
    if (parent) {
        graph[node->val][graphSize[node->val]++] = parent->val;
        graph[parent->val][graphSize[parent->val]++] = node->val;
    }
    buildGraph(node->left, node, graph, graphSize);
    buildGraph(node->right, node, graph, graphSize);
}

int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize) {
    int graph[501][3];
    int graphSize[501];
    memset(graphSize, 0, sizeof(graphSize));
    buildGraph(root, NULL, graph, graphSize);
    bool visited[501] = {false};
    int queue[501], front = 0, back = 0;
    queue[back++] = target->val;
    visited[target->val] = true;
    int dist = 0;
    while (front < back && dist < k) {
        int size = back - front;
        for (int i = 0; i < size; i++) {
            int u = queue[front++];
            for (int j = 0; j < graphSize[u]; j++) {
                int v = graph[u][j];
                if (!visited[v]) { visited[v] = true; queue[back++] = v; }
            }
        }
        dist++;
    }
    *returnSize = back - front;
    int* res = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++) res[i] = queue[front + i];
    return res;
}

js

/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function (root, target, k) {
  const graph = new Map()
  const build = (node, parent) => {
    if (!node) return
    if (!graph.has(node.val)) graph.set(node.val, [])
    if (parent !== null) {
      graph.get(node.val).push(parent.val)
      if (!graph.has(parent.val)) graph.set(parent.val, [])
      graph.get(parent.val).push(node.val)
    }
    build(node.left, node)
    build(node.right, node)
  }
  build(root, null)
  const visited = new Set([target.val])
  let queue = [target.val]
  let dist = 0
  while (queue.length && dist < k) {
    const next = []
    for (const u of queue) {
      for (const v of graph.get(u) || []) {
        if (!visited.has(v)) {
          visited.add(v)
          next.push(v)
        }
      }
    }
    queue = next
    dist++
  }
  return queue
}

py

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        from collections import defaultdict, deque
        graph = defaultdict(list)
        def build(node, parent):
            if not node: return
            if parent:
                graph[node.val].append(parent.val)
                graph[parent.val].append(node.val)
            build(node.left, node)
            build(node.right, node)
        build(root, None)
        visited = {target.val}
        queue = deque([target.val])
        for _ in range(k):
            for _ in range(len(queue)):
                u = queue.popleft()
                for v in graph[u]:
                    if v not in visited:
                        visited.add(v)
                        queue.append(v)
        return list(queue)

• 时间复杂度：$O(n)$，其中 n 是节点数
• 空间复杂度：$O(n)$

算法思路：

• DFS 将二叉树转为无向图（每个节点与父节点双向连接）
• 从 target 出发做 BFS，扩展 k 层后的节点即为答案